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

Schedule

Dear readers,

We started this blog with weekly posts. The idea was for this blog to be the go-to place for news from the matroid theory community, and we felt that a weekly schedule would help with that. Unfortunately, a weekly schedule also places a burden on the writers, and we received feedback from some readers, who indicated they had trouble keeping up with the blog at this pace.

For these reasons, we are going to reduce the frequency of posts a little. We’re aiming for a post every two weeks. New posts will, as always, be announced in a few places:

  • Through the RSS feed, which can be followed using RSS readers like Feedly, just like any other blog.
  • Through email, for which you can sign up at the top right of the blog’s main page.
  • Through Twitter, by following @matroidunion.

If you want to help out, we welcome guest posts. You can base your post on this template (just download to your computer, and edit in your favorite text editor).

Tune in next time for another guest post by Jim Geelen!

Proving nonexistence of some projective planes

In this post the matroid theory connections are everywhere, but I won’t use any matroid language. Can you spot them all?

I’m going to discuss my favorite lecture from the course MAT377 – Introduction to Combinatorics, which I have taught at Princeton in the past three years (lecture notes can be found here). This particular lecture was not part of the first run of the course, but inspired by it. After introducing the MacWilliams relations in coding theory (see below), I was asked by my students what they can be used for. The coding theory books that I consulted were not much help, although they claimed them to be deep, important, etc. But an email to Peter Cameron, and then an answer from Chris Godsil on Mathoverflow, led me to the paper [AM78], in which Assmus and Maher prove the following (and slightly more, but I try to keep this post as short as possible).

Theorem 1. There is no projective plane of order $q$, where $q \equiv 6 \pmod 8$.

Preliminaries

We need some design theory, coding theory, and linear algebra in our proof. Recall that a $t-(v,k,\lambda)$ design is a collection of subsets of a set of $v$ points (subsets can be repeated more than once), where each subset (or block) has size $k$, and every subset of $t$ points is contained in exactly $\lambda$ blocks. So in this terminology, a projective plane of order $q$, where the blocks are taken to be the lines, would be a $2-(q^2+q+1,q+1,1)$ design. Other parameters of the design include the number of blocks $b$, and the replication number $r$, the number of blocks containing a single point. One can show that $b$ and $r$ are determined by the parameters of the design, and that $r$ does not depend on the point chosen. The block-point incidence matrix of a design is the matrix $A$ with rows indexed by blocks, columns by points, and
$$
A_{ij} = \begin{cases} 1 & \text{ if point } j \text{ is in block } i\\
0 & \text{ otherwise.}\end{cases}
$$

Exercise 1. Let $A$ be the block-point incidence matrix of a design. Show that for a $2-(v,k,\lambda)$ design with $v=b$, we have the following:

  • $k=r$
  • $k(k-1) = \lambda(v-1)$
  • $AA^T = A^TA$
  • $|\det(A)| = k(k-\lambda)^{(v-1)/2}$
  • Every two blocks meet in exactly $\lambda$ points

Misleadingly, such designs are called symmetric. Note that $A$ need not be a symmetric matrix at all!

A $q$-ary linear $[n,k,d]$ code $C$ is a linear subspace of $\mathrm{GF}(q)^n$ of dimension $k$. Think of it as the row space of a matrix. The elements of $C$ are called codewords, and the weight of a codeword $c \in C$ is $\mathrm{wt}(c) = |\{i : c_i\neq 0\}|$. The parameter $d$ of the code is the minimum weight of the nonzero codewords in $C$. Since weights are related to the Hamming distance between codewords (and thus to the error-correcting capabilities of the code), it makes sense to study the weight enumerator:
$$
W_C(x,y) := \sum_{c\in C} x^{\mathrm{wt}(c)}y^{n – \mathrm{wt}(c)}.
$$

The dual code is $C^\perp$, the orthogonal complement of the vector space $C$. We can derive the following relation between the weight enumerators of $C$ and $C^\perp$:

Theorem 2 (MacWilliams Relations).
$$
W_{C^\perp}(x,y) = q^{-k} W_C(y-x, y+ (q-1)x).
$$

From linear algebra we require the Smith Normal Formof which we will only use the following restricted version:

Theorem 3. Let $A$ be an $n\times n$ nonsingular matrix over $\mathbb{Z}$. There exist integer matrices $M, N$ with $\det(M) = \det(N) = 1$, and $MAN = D$, where $D$ is a diagonal matrix with diagonal entries $d_1, \ldots, d_n$ such that $d_{i} | d_{i+1}$ for $i = 1, \ldots, n-1$.

The proof.

We start with two lemmas.

Lemma 1. Let $A$ be the incidence matrix of a symmetric $2-(v,k,\lambda)$ design. Let $A_+$ be obtained from $A$ by adding an all-ones column, and let $C$ be the binary linear code generated by the rows of $A_+$. If $k$ is odd, $k-\lambda$ is even, but $k-\lambda$ is not a multiple of $4$, then $C$ is a $[v+1, (v+1)/2, d]$ code for some $d$, and $C^\perp = C$.

Proof. Interpret $A$ as an integer matrix. Let $M, N$ be as in Theorem 3. Then $d_1d_2 \cdots d_n = \det(MAN) = \det(A) = \pm k(k-\lambda)^{(v-1)/2}$. Since $k$ is odd, and each factor $(k-\lambda)$ contributes one factor $2$, no more than $(v-1)/2$ of the $d_i$ are are divisible by $2$. Hence, writing $r_\mathbb{F}$ for matrix rank over the field $\mathbb{F}$, we have
$$
r_{\mathrm{GF}(2)}(A_+) \geq r_{\mathrm{GF}(2)}(A) = r_{\mathrm{GF}(2)}(MAN) \geq (v+1)/2.
$$

Conversely, let $a$ and $b$ be rows of $A_+$. The inner product of $a$ with itself is $\langle a, a\rangle = k + 1 \equiv 0 \pmod 2$. Also, $\langle a,b\rangle = \lambda + 1 \equiv 0 \pmod 2$. It follows by linearity that each codeword in $C$ is orthogonal to every codeword in $C$, i.e. $C \subseteq C^\perp$. Since $\dim(C) + \dim(C^\perp) = v+1$, it follows that $r_{\mathrm{GF}(2)}(A_+) \leq (v+1)/2$, so equality must hold. $\square$

A code is doubly even if all weights are multiples of four.

Lemma 2. If $C$ is a binary, linear $[v+1,(v+1)/2, d]$, self-dual, doubly even code, then $8|(v+1)$.

Proof. For a binary linear $[n,k,d]$ code, the MacWilliams relations specialize to
$$
W_{C^\perp}(x,y) = 2^{-k}W_C(y-x,y+x) = 2^{n/2 – k} W_C( (x,y)\sigma),
$$
where $\sigma$ is the linear transformation
$$
\sigma = \frac{1}{\sqrt{2}}\begin{bmatrix} -1 & 1\\ 1 & 1\end{bmatrix}.
$$
If $C$ is self-dual, then $W_C$ is invariant under $\sigma$. If $C$ is doubly even, then $W_C$ is also invariant under
$$
\pi = \begin{bmatrix} i & 0 \\ 0 & 1 \end{bmatrix},
$$
where $i \in \mathbb{C}, i^2 = -1$. Now $W_C$ is invariant under the group generated by $\sigma$ and $\pi$, and in particular under
$$(\pi\sigma)^3 = \frac{1+i}{\sqrt{2}}\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}.$$
Since this transformation multiplies each of $x$ and $y$ by a primitive eighth root of unity, the result follows.$\square$

Proof of Theorem 1. Suppose a binary projective plane of order $q \equiv 6 \pmod 8$ exists. Consider the corresponding $2-(q^2+q+1,q+1,1)$ design, its incidence matrix $A$, and the binary, linear code $C$ generated by $A_+$ as above. By Lemma 1, $C$ is self-dual. Each row of $A_+$ has $q+2$ nonzero entries, and therefore weight $0 \pmod 4$. Since $C$ is self-dual, any two codewords intersect in an even number of positions, and it follows that all codewords have weight $0 \pmod 4$. By Lemma 2, then, $v+1 = q^2 + q + 2$ is divisible by $8$, which contradicts the assumption that $q \equiv 6 \pmod 8$. $\square$

Note that the MacWilliams relations also played a big role in determining the nonexistence of a projective plane of order 10.

Problem. Are techniques like the ones used above applicable elsewhere in matroid theory?

[AM78] Assmus, E. F., Jr.; Maher, David P. Nonexistence proofs for projective designs. Amer. Math. Monthly 85 (1978), no. 2, 110–112