Guest post by Jim Geelen
$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\bF}{\mathbb{F}}$ $\newcommand{\cL}{\mathcal{L}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\DeclareMathOperator{\ex}{ex}$ $\DeclareMathOperator{\PG}{PG}$ $\DeclareMathOperator{\AG}{AG}$ $\DeclareMathOperator{\BB}{BB}$
In my last post I discussed the Turán problem for the binary projective geometry $\PG(m-1,2)$. We saw that chromatic number plays a significant role in Turán problems for graphs and that critical exponent plays an important role in Turán problems on binary geometries. This time I will consider the Turán problem for the binary affine geometry $\AG(m-1,2)$. Affine geometries have critical exponent one, so they are analogous to complete bipartite graphs.
Avoiding a bipartite graph
Recall that a graph is called $H$-free if it has no subgraph isomorphic to $H$. The Turán problem for a given graph $H$ is to determine, for each integer $n$, the maximum number, $\ex(H,n)$, of edges among all $n$-vertex $H$-free graphs.
Erdös and Stone [ES46] proved that, for each bipartite graph $H$, $\ex(H,n) = o(n^2)$.
Theorem:
Let $H$ be a bipartite graph and $\epsilon>0$ be a real number. Then, for each sufficiently large integer $n$, if $G$ is an $n$-vertex graph with $|E(G)|\gt \epsilon n^2$, then $G$ has a subgraph isomorphic to $H$.
For bipartite $H$, computing $\ex(H,n)$ exactly is notoriously difficult. For example, the Turán numbers are not known for the $4$-circuit, $K_{2,2}$, although the asymptotic behaviour is known. Results of Erdös, Rényi, and Sós [ERS66] and Brown [Bro66] show that $$ \ex(K_{2,2},n) = \frac 1 2 n^{3/2} + o(n^{3/2}). $$ For $K_{4,4}$ the situation is worse; we do not even know the asymptotic behaviour.
Avoiding an affine geometry
The Geometric Density Hales-Jewett Theorem, proved by Furstenberg and Katznelson [FK85], is one of the gems of Ramsey Theory and of extremal matroid theory, although it took some time for matroid theorists to recognize its existence. The gist of the result is that, if we take a fixed fraction of all points in a sufficiently large projective geometry, the chosen points will contain a copy of any fixed affine geometry.
Geometric Density Hales-Jewett Theorem.
Let $\bF$ be a finite field of order $q$, let $m$ be an integer, and let $\epsilon>0$ be a real number. Then, for any sufficiently large integer $n$, if $M$ is a simple rank-$n$ $\bF$-representable matroid with $|M|> \epsilon q^n$, then $M$ has a restriction isomorphic to $\AG(m-1,\bF)$.
In this post we are primarily interested in binary geometries. Recall that a binary geometry is called $N$-free if it has no restriction isomorphic to $H$. The Turán problem for a given binary geometry $N$ is to determine, for each integer $r$, the maximum number, $\ex(N,r)$, of points among all rank-$r$ $N$-free binary geometries. In this terminology, the Binary Density Hales-Jewett Theorem says that $\ex(\AG(m-1,2),r)$ is $o(2^r)$.
Binary Density Hales-Jewett Theorem.
Let $m$ be an integer and let $\epsilon>0$ be a real number. Then, for any sufficiently large integer $n$, if $M$ is a rank-$n$ binary geometry with $|M|> \epsilon q^n$, then $M$ has a restriction isomorphic to $\AG(m-1,2)$.
Furstenberg and Katznelson’s proof is very difficult, but the first step is a straightforward reduction to the case that $m=2$. Now $\AG(1,\bF)$ is a $q$-point line, so, when $q=2$, there is nothing more to do. We will sketch a simpler proof, due to Bonin and Qin [BQ00], for the Binary Density Hales-Jewett Theorem.
Lemma.
For each real number $\epsilon>0$ and sufficiently large integer $r>0$, if $X$ is a set of $\ge \epsilon 2^r$ points in $\PG(r-1,2)$, then there is a point $p$ in $\PG(r-1,2)$ and a set $\cL$ of $\ge \epsilon^2(1-\epsilon) 2^{r-1}$ lines each containing $p$ as well as two other points in $X$.
Proof.
We take $r$ large enough that $\epsilon 2^r – 1\ge (1-\epsilon)\epsilon (2^r-1)$. There are $|X|(|X|-1)\ge (\epsilon 2^r)(\epsilon 2^r-1) \ge \epsilon^2(1-\epsilon) 2^r(2^r-1)$ ordered triples $(x,y,z)$ of points in $\PG(r-1,2)$ such that $\{x,y,z\}$ is a triangle and $x,y\in X$. So thare are at least $\epsilon^2(1-\epsilon) 2^r$ such triples with the same third point. This proves the lemma. $\Box$
Now, to prove the theorem, consider projecting from $p$. The lines in $\cL$ give a collection $X’$ of $\epsilon^2 (1-\epsilon) 2^{r-1}$ points in $\PG(r-2,2)$. Moreover, if $\PG(r-2,2)|X’$ contains a copy of $\AG(m-2,2)$, then $\PG(r-1,2)$ contains a copy of $\AG(m-1,2)$. Therefore the result follows easily by induction.
Open problems
The Binary Density Hales-Jewett Theorem falls well short of resolving the Turán problem for binary affine geometries. The Turán problem for bipartite graphs is notably difficult, as too is the problem of determining the convergence rates in the Geometric Density Hales-Jewett Theorem. Set against this, the Turán problem for binary affine geometries does not look very promising. On the other hand, the proof of the Binary Density Hales-Jewett Theorem is very easy, and there has not been a lot of work on determining the asymptotic behaviour; the only paper that I know of on the topic is that of Bonin and Qin [BQ00]. They give a reasonable upper bound, in general, but they only give a lower bound for the $4$-circuit, $\AG(2,2)$.
A more careful version of the above proof of the Binary Density Hales-Jewett Theorem gives the following bound; see [BQ00, Lemma 21].
Theorem.
For integers $n\ge m\ge 3$,
$$ \ex(\AG(m-1,2), r) \lt 2^{\alpha_m r +1},$$
where $\alpha_m = 1-2^{-(m-2)}$.
For the $4$-circuit, Bonin and Qin prove the following; see [BQ00, Lemmas 19 and 21].
Theorem.
For each integer $n\ge 3$,
$$ 6^{1/3}2^{r/3}\le \ex(\AG(2,2), r) \lt 2^{\frac r 2 +1}.$$
What is the asymptotic behviour of $\ex(\AG(2,2), r)$?
References
[BQ00] J.E. Bonin, H. Qin, Size functions of subgeometry-closed classes of representable combinatorial geometries, Discrete Math. 224 (2000).
[Bro66] W.G. Brown, On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 (1966).
[ERS66] P. Erdös, A. Rényi, V.T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar. 1 (1966).
[ES46] P. Erdös, A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946).
[FK85] H. Furstenberg, Y. Katznelson, An ergodic Szemeredi theorem for IP-systems and combinatorial theory, J. d'Analyse Mathématique 45 (1985).