The Geometric Density Hales-Jewett Theorem

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).

6 thoughts on “The Geometric Density Hales-Jewett Theorem

  1. It seems like bad form to comment on one’s own post, but…

    Let $f(r)$ be the maximum number of elements in a binary geometry with girth at least $5$. It is easy to prove that
    $$ f(r) \le ex(AG(2,2),r) \le \frac{3}{2} f(r).$$
    Indeed, the first inequality is trivial and the second follows from the fact that no element in an $AG(2,2)$-free binary geometry is in two triangles.

    Now $f(r)$ is, evidently, of interest to coding theorists, so I asked Navin Kashyap. It turns out that BCH codes give a very good lower bound. From this, for even $r$, you get:
    $$ f(r) (f(r)+1) \le 2^r \le (f(r)+1)^2. $$

    • Yes, the extremal ones do have triangles, sometimes quite a few. The 10 examples of size 24 at rank 9 have from 2 to 6 triangles.

      Yes, also to the rank r+2 examples containing as restrictions the rank r ones; at least it happens, but I haven’t done a systematic check of whether it happens in every case.

      I’ll try to go from one size 18 example of rank 8 up to rank 10, aiming to hit size 36.

  2. So this shows that the asymptotic growth rate is $O(2^{r/2})$ then (at least for even $r$).

    At the other end of the spectrum, my computer gives me the following numbers of the maximum size of an $AG(2,2)$-restriction-free simple binary matroid of rank $r$: rank 4 – 6, rank 5 – 7, rank 6 – 9, rank 7 – 12, rank 8 – 18, rank 9 – 24. Ignoring the small ranks we get a nice doubling of the size for each increase of 2 in the rank. And rank 10 is out of my range.

    Unfortunately the extremal examples don’t appear to have any obvious nice structure that might lead to an explicit family close up to the bound.

    • Interesting.

      Do the extremal examples have triangles?

      Also, do extremal examples in rank 8 contain extremal examples in rank 6? If so, would you program be able to check rank-10 examples containing rank-8 examples?

    • I looked up coding theory data-bases for the maximum number $f(r)$ of elements in a simple rank-$r$ matroid with girth at least $5$. They have $f(6) = 8$, $f(7)=11$, $f(8)=17$, and $f(9)=23$; one less than your numbers in each case. They also know that $f(10)=33$.

      • Yes, the extremal ones do have triangles, sometimes quite a few. The 10 examples of size 24 at rank 9 have from 2 to 6 triangles.
        (Same comment as above, but just in the correct part of the thread!)

        Yes, also to the rank r+2 examples containing as restrictions the rank r ones; at least it happens, but I haven’t done a systematic check of whether it happens in every case.

        I’ll try to go from one size 18 example of rank 8 up to rank 10, aiming to hit size 36.

Leave a Reply

Your email address will not be published. Required fields are marked *