A geometric version of the Andrasfai-Erdos-Sos theorem

Abstract

For each odd integer $k\ge 5$, we prove that, if $M$ is a simple rank-$r$ binary matroid with no odd circuit of length less than $k$ and with $|M|>k{2}^{r-k+1}$, then $M$ is isomorphic to a restriction of the rank-$r$ binary affine geometry; this bound is tight for all $r\ge k-1$. We use this to give a simpler proof of the following result of Govaerts and Storme: for each integer $n\ge 2$, if $M$ is a simple rank-$r$ binary matroid with no $PG(n-1,2)$-restriction and with $|M|>\left(1-\frac{11}{2^{n+2}}\right)2^r$, then $M$ has critical number at most $n-1$. That result is a geometric analogue of a theorem of Andrasfai, Erdos, and Sos in extremal graph theory.

8 pages, revised title, minor corrections to the first version

Cited by in corpus (1)

• Stability and exact Turan numbers for matroids