pith. sign in

arxiv: 1710.03815 · v1 · pith:5EUS2MWBnew · submitted 2017-10-10 · 🧮 math.CO

Stability and exact Turan numbers for matroids

classification 🧮 math.CO
keywords bounderrortermcloseextremalgivesmathbbresult
0
0 comments X
read the original abstract

We consider the Tur\'an-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\H{o}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|$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.