Stability and exact Turan numbers for matroids

Abstract

We consider the Turán-type problem of bounding the size of a set $M\subseteq {\mathbb{F}}_2^n$ that does not contain a linear copy of a given fixed set $N\subseteq {\mathbb{F}}_2^k$, where $n$ is large compared to $k$. An Erdős-Stone type theorem [5] in this setting gives a bound that is tight up to a $o(2^n)$ error term; our first main result gives a stability version of this theorem, showing that such an $M$ that is close in size to the upper bound in [5] is close in edit distance to the obvious extremal example. Our second result shows that the error term in [5] is exactly controlled by the solution to one of a class of `sparse' extremal problems, and in many cases eliminates the error term completely to give a sharp upper bound on $|M|$.