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{\rank}{rank}$ $\DeclareMathOperator{\PG}{PG}$ $\DeclareMathOperator{\AG}{AG}$ $\DeclareMathOperator{\BB}{BB}$

In my last two posts I discussed the Turán problems for the binary projective geometry and for the binary affine geometry. This time I will consider the Turán problem for an arbitrary binary geometry. An extraordinary connection between Turán densities and critical exponents emerges.

Graphs

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.

The following result, due to Erdös and Stone [ES46], is among my favourite theorems in extremal graph theory. It reveals an unexpected connection between the chromatic number of a graph and the asymptotic behaviour of its Turán numbers.

Erdös-Stone Theorem: Let $H$ be a graph with chromatic number $\chi\ge 2$. Then $$ \lim_{n\rightarrow\infty} \frac{\ex(H,n)}{|E(K_n)|} = \frac{\chi-2}{\chi-1}.$$

Note that the Turán graphs $T(n,\chi)$ are $H$-free and have densities approaching $\frac{\chi-2}{\chi-1}.$

The Erdös-Stone Theorem shows that $\ex(H,n) = \frac{\chi-2}{\chi-1}{n\choose 2} + o(n^2)$, which gives the asymptotic behaviour of $\ex(H,n)$ except when $\chi=2$. Determining the asymptotic behaviour of the Turán numbers of bipartite graphs is a difficult open problem, which I discussed last time.

Binary Geometries

Recall that a binary geometry is called $N$-free if it has no restriction isomorphic to $N$. 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. The Bose-Burton geometry $\BB(r,c)$ is the binary geometry obtained from $\PG(r-1,2)$ by deleting all of the points in a flat of rank $r-c$.

The following result relates the critical exponent of a binary geometry and the asymptotic behaviour of its Turán numbers; see [GN].

Geometric Erdös-Stone Theorem: Let $N$ be a binary geometry with critical exponent $c\ge 1$. Then $$ \lim_{r\rightarrow\infty} \frac{\ex(N,r)}{|\PG(r-1,2)|} = 1-2^{-(c-1)}.$$

Note that the Bose-Burton geometries $\BB(r,c-1)$ are $N$-free and have densities approaching $1-2^{-(c-1)}.$

The Geometric Erdös-Stone Theorem shows that $\ex(N,r) = 2^r – 2^{r-c+1} + o(2^r)$, which gives the asymptotic behaviour of $\ex(N,r)$ except when $c=1$. When $c=1$, the result is implied by the Binary Density Hales-Jewett Theorem which we proved last time.

We reformulate the Geometric Erdös-Stone Theorem below to facilitate its proof. The proof is a bit on the heavy side for a blog post, but it is surprizingly short considering the result, and it is easier than the proof of the Erdös-Stone Theorem.

Theorem: Let $c\ge 1$ be an integer. Then, for each integer $m\gt c$ and real number $\epsilon>0$, $$\ex( \BB(m,c); r) \lt (1- 2^{-(c-1)}+\epsilon) |\PG(r-1,2)|,$$ for all sufficiently large $r$.

Proof Sketch. The proof is by induction on $c$; the case that $c=1$ follows directly from the Binary Density Hales-Jewett Theorem. So we may assume that $c\gt 1$ and that the result holds for $c-1$.

Let $m\gt c$ be an integer, let $\epsilon\gt 0$ be a real number, and let $r\gg n$ be large integers. Now let $M$ be a rank-$r$ binary geometry with $|M| \ge (1-2^{-(c-1)}+\epsilon) |\PG(r-1,2)|$. By the inductive assumption, $M$ has a $\BB(n,c-1)$-restriction. Consider $M$ as a restriction of $\PG(r-1,2)$. Thus there are flats $F_0\subseteq F_1$ of $\PG(r-1,2)$ such that $\rank(F_1)=n$, $\rank(F_0)=n-c+1$, and $F_1-F_0\subseteq M$.

So by an easy averaging argument, there exists a rank-$(n+1)$ flat $F_2$ containing $F_1$ such that $$|M\cap(F_2-F_1)| \ge \left(1-2^{1-c} +\frac{\epsilon}{2}\right)|F_2-F_1| = (1-2^{1-c})2^{n} +\frac{\epsilon}{2} 2^n .$$

For a flat $F$ of $\PG(r-1,2)$ and point $e\not\in F$, we let $F+e$ denote the flat spanned by $F\cup\{e\}$. Let $e\in F_2-F_1$ and let $Q_0 = (F_0+e)-F_0$. Now let $F_0^c\subseteq F_1$ be a rank-$(c-1)$ flat that is disjoint from $F_0$. Now let $S= (F_2-F_1)\cap E(M)$ and, for each $f\in Q_0$, let $S_f = (F_0^c + f)\cap S$. Note that $(S_f\, : \, f\in Q_0)$ partitions $S$ and $|S_f|\le 2^{c-1}$. By another easy averaging argument, there is a $\frac{\epsilon}{2} 2^n$-element subset $Q_1$ of $Q_0$ such that $|S_f|= 2^{c-1}$ for each $f\in Q_1$. By the Binary Density Hales-Jewett Theorem, there is a subset $Q_2$ of $Q_1$ such that $M|Q_2 \cong \AG(m-c, 2)$. Let $F$ be the flat of $\PG(n-1,2)$ spanned by $F_0^c$ and $Q_2$. Thus $F$ has rank $m$, $F_0^c\subseteq F$, and, since $Q_2\subseteq Q_1$, $F-F_1\subseteq M$. So the restriction of $M$ to $F-F_0$ gives $\BB(m,c)$, as required. $\Box$

Open problem

Bonin and Qin [BQ00] determine exact values for the Turán numbers for several classes of geometries. There are many other natural classes that are yet to be considered; this might be an interesting avenue for further research. I will conclude with one problem in that direction. We call a binary geometry $c$-critical if it has critical exponent $c$ and each of its proper restrictions has critical exponent $\lt c$.

Conjecture: For any $c$-critical binary geometry $N$, $\ex(N,r) = 2^r – 2^{r-c+1},$ for all sufficiently large $r$.

References

[BQ00] J.E. Bonin, H. Qin, Size functions of subgeometry-closed classes of representable combinatorial geometries, Discrete Math. 224 (2000).

[ES46] P. Erdös, A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946).

[GN] J. Geelen, P. Nelson, An analogue of the Erdös-Stone Theorem for finite geometries, arXiv:1203.1911