Simple Matroids with Bounded Cocircuit Size

• Published in: Combinatorics, probability & computing probability & computing, 2000-09, Vol.9 (5), p.407-419, Article S0963548300004429
• Main Authors: BONIN, JOSEPH E., REID, TALMAGE JAMES
• Format: Article
• Language: English
• ISSN: 0963-5483; 1469-2163
• DOI: 10.1017/S0963548300004429

We examine the specialization to simple matroids of certain problems in extremal matroid theory that are concerned with bounded cocircuit size. Assume that each cocircuit of a simple matroid M has at most d elements. We show that if M has rank 3, then M has at most d + [lfloor ]√d[rfloor ] + 1 points, and we classify the rank-3 simple matroids M that have exactly d + [lfloor ]√d[rfloor ] points. We show that if M is a connected matroid of rank 4 and d is q3 with q > 1, then M has at most q3 + q2 + q + 1 points; this upper bound is strict unless q is a prime power, in which case the only such matroid with exactly q3 + q2 + q + 1 points is the projective geometry PG(3, q). We also show that if d is q4 for a positive integer q and if M has rank 5 and is vertically 5-connected, then M has at most q4 + q3 + q2 + q + 1 points; this upper bound is strict unless q is a prime power, in which case PG(4, q) is the only such matroid that attains this bound.