MATROIDS WITH NO strongqstrong +2)-POINT-LINE MINORS.pdfVIP

MATROIDS WITH NO (q + 2)-POINT-LINE MINORS JOSEPH E. BONIN ABSTRACT. It is known that a geometry with rank r and no minor isomorphic to the (q + 2)-point line has at most (qr − 1)/(q − 1) points, with strictly fewer points if r 3 and q is not a prime power. For q not a prime power and r 3, we show that qr −1 − 1 is an upper bound. For q a prime power and r 3, we show that any rank-r geometry with at least qr −1 points and no (q + 2)-point-line minor is representable over G(q). We strengthen these bounds to qr −1 − (qr −2 − 1)/(q − 1) − 1 and qr −1 − (qr −2 − 1)/(q − 1) respectively when q is odd. We give an application to unique representability and a new proof of Tutte’s theorem: A matroid is binary if and only if the 4-point line is not a minor. 1. SOME EXTREMAL MATROIDS : PROJECTIVE AND AFFINE GEOMETRIES We are concerned with matroids containing no minor isomorphic to the (q + 2)-point line, i.e., the uniform matroid U2,q+2 . These matroids form a minor-closed class, denoted U (q). This class is of interest in part because of its connections with representability questions and its role in extremal matroid theory, in particular, in connection with size functions (see Section 4.2 of [6], especially Corollary 4.5). If q is a prime power, then L(q) ⊆ U (q), where L(q) is the class of matroids representable over G(q). Tutte [10] proved that L(2) = U (2). The containment is strict for all other prime powers q. The starting point for our work is the following result [6, Theorem 4.3]. Theorem 1. Rank-r geometries in U (q) have at most (qr −1)/(q −1)points. This upper bound is attained only by projective geometries of order q. Thus for r 3, this bound is attained if and only if q is a prime power. To set