The Bose-Burton Theorem

$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\DeclareMathOperator{\ex}{ex}$ $\DeclareMathOperator{\PG}{PG}$ $\DeclareMathOperator{\AG}{AG}$
$\DeclareMathOperator{\BB}{BB}$

Note: next week there will be no post. The Matroid Union will return on January 6 with a post by Stefan. Happy holidays!

Guest post by Jim Geelen.

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. This problem has a natural analogue for binary geometries (that is, simple binary matroids). A binary geometry is called $N$-free if it has no restriction isomorphic to $N$. The Turán problem for a binary geometry $N$ is to determine, for each integer $r$, the maximum number, $\ex(N,r)$, of points in a rank-$r$ $N$-free binary geometry.

Geometers have done quite a lot of work on Turán problems for projective geometries (see [HS01, Section 7]), but it does not seem to be well known in matroid theory (I didn’t know about it in any case). The purpose of this post is to discuss the Bose-Burton Theorem [BB66], which solves the Turán problem for projective geometries, and to consider questions about the structure of $\PG(m-1,2)$-free binary geometries that are close to the density threshold.

$K_t$-free graphs

We start with the classical result of Turán.

The Turán graph $T(n,t)$ is the complete $(t-1)$-partite graph whose parts each have size $\lfloor{\frac{n}{t-1}}\rfloor$ or $\lceil{\frac{n}{t-1}}\rceil$. Equivalently, $T(n,t)$ is the densest $(t-1)$-colourable graph on $n$ vertices. Since $T(n,t)$ is $(t-1)$-colourable, it is $K_t$-free. Let $\tau(n,t)$ denote the number of edges of $T(n,t)$.

Turán’s Theorem: For all integers $n\ge t\ge 1$, if $G$ is a $K_t$-free graph with $n$ vertices, then $|E(G)|\le \tau(n,t)$. Moreover equality holds if and only if $G$ is isomorphic to $T(n,t)$.

$\PG(m-1,2)$-free geometries

The Bose-Burton geometry , denoted $\BB(r,c)$, is the geometry obtained from $\PG(r-1,2)$ by deleting all of the points in a flat of rank $r-c$. Thus $\BB(r,1)$ is isomorphic to the binary affine geometry $\AG(r-1,2)$. Note that $\BB(r,c)$ has $2^r – 2^{r-c}$ points. The critical exponent of a rank-$r$ binary geometry $M$ is the minimum $c$ such that $M$ is isomorphic to a restriction of $\BB(r,c)$. Thus $\BB(r,c)$ is the densest rank-$r$ binary geometry with critical exponent $c$.

Bose-Burton Theorem: For all integers $r\ge m\ge 1$, if $G$ is a $\PG(m-1,2)$-free binary geometry with rank $r$, then $|M|\le 2^r – 2^{r-m+1}.$ Moreover equality holds if and only if $M$ is isomorphic to $\BB(r,m-1)$.

The result is easier to prove in the following form.

Theorem: For all integers $r\ge m\ge 1$, if $X$ is a set of points in $\PG(r-1,2)$ such that $\PG(r-1,2)\del X$ is $\PG(m-1,2)$-free, then $|X| \ge 2^{r-m+1} -1$. Moreover, $|X| = 2^{r-m+1} -1$ if and only if $X$ is a rank $r-m+1$ flat of $\PG(r-1,2)$.

Proof. Consider a counterexample $(r,m,X)$ with $m$ as small as possible; clearly $m\gt 1$. Let $p\not\in X$ be a point of $\PG(r-1,2)$; if $X$ is not a flat of $\PG(r-1,2)$, then we choose $p$ to be on a line spanned by two points in $X$. When we contract $p$ in $\PG(r-1,2)$ and simplify we get $\PG(r-2,2)$; let $X’$ be the image of $X$ under this contraction. By construction $\PG(r-2,2)-X’$ is $\PG(m-2,2)$-free. By our choice of counterexample, $$ |X’|\ge 2^{r-1 – {m-1} + 1} -1 = 2^{r-m+1}-1.$$ Moreover, by construction, $ |X| \ge |X’|$ and, by our choice of $p$, unless $X$ is a flat of $\PG(r-1,2)$, $ |X| \gt |X’|.$ This proves the result.$\Box$

Turán’s Theorem has some quite easy proofs, but none are as simple as the above proof of the Bose-Burton Theorem.

Graphs near the threshold

The density of an $n$-vertex graph with $m$-edges is defined to be $\frac{m}{n\choose 2}$. Note that, for large $n$ the density of the Turán graph $T(n,t)$ tends to $\frac{t-2}{t-1}$ (this is the probability that two randomly chosen vertices fall in distinct classes).

Turán’s Theorem gives a density threshold for $K_t$-free graphs and characterizes those graphs that meet the threshold; the characterization amounts to saying that the extremal graphs are $(t-1)$-colourable. One might hope that all $K_t$-free graphs with density close to $\frac{t-2}{t-1}$ are $(t-1)$-colourable, however, this turns out to be false. There exist triangle-free graphs that are not $(t-1)$-colourable, and by taking the direct sum with such a graph with a large Turán graph $T(n,t)$, we can get $K_t$-free graphs that are not $(t-1)$-colourable and whose densities are arbitrarily close to $\frac{t-2}{t-1}$.

Andrásfai, Erdös, and Sós [AES74] overcome this by considering the minimum degree instead of the density. Note that an $n$-vertex graph with minimum degree $\ge d\cdot n$ has density $\gt d$.

Theorem: If $G$ is a $K_t$-free graph on $n$-vertices with minimum degree $\ge \frac{3t-7}{3t-4} n$, then $G$ is $(t-1)$-colourable.

It may not be immediately obvious, but $\frac{3t-7}{3t-4} < \frac{t-2}{t-1}$. For example, the density threshold for $K_3$-free graphs is $\frac{t-2}{t-1} = \frac{1}{2}$, and the above theorem says that $n$-vertex $K_3$-free graphs with minimum degree $> \frac{3t-7}{3t-4}n = \frac 2 5 n$ are bipartite.

Geometries near the threshold

The density of a rank-$r$ binary geometry with $m$ points is defined to be $\frac{m}{2^r-1}$. Note that, for large $r$ the density of the Bose-Burton geometry $\BB(r,m-1)$ tends to $1-2^{1-m}$.

The Bose-Burton Theorem gives a density threshold and shows that the extremal $\PG(m-1,2)$-free binary geometries have critical exponent $m-1$. It turns out that, unlike the case for graphs, all $\PG(m-1,q)$-free binary geometries with density close to $1-2^{1-m}$, have critical exponent $m-1$. The following result is due to Goevaerts and Storme [GS06].

Theorem: For all integers $r\ge m\ge 2$, if $M$ is a rank-$r$ $\PG(m-1,2)$-free binary geometry with $|M| > \left(1-\frac{11}{2^{m+2}}\right)2^r$, then $M$ has critical exponent $\le m-1$.

The bound in the above theorem is sharp; see [GS06]. This result is particular to the binary field; Beutelspacher [Beu80] gives a bound for arbitrary fields, but that bound is only sharp for fields of square order.

Triangle-free graphs

The following striking sequence of results on triangle-free graphs begs for an analogue in the context of binary geometries.

  • There is no $n$-vertex triangle-free graph with minimum degree $\gt \frac 1 2 n$.
  • Every $n$-vertex triangle-free graph with minimum degree $\gt \frac 2 5 n$ is bipartite; see [AES74].
  • Every $n$-vertex triangle-free graph with minimum degree $\gt \frac{10}{29}n$ is three-colourable; see [Jin95].
  • Every $n$-vertex triangle-free graph with minimum degree $\gt \frac{1}{3}n$ is four-colourable; see [BT].
  • For each $d\lt \frac 1 3$ there exist triangle-free graphs $G$ with minimum degree $\gt d |V(G)|$ and arbitrarily large chromatic number; proved by Hajnal, see [ES73].

The above results solve a problem of Erdös and Simonovits for triangle-free graphs. The following question is a geometric analogue of that problem.

Question: For integers $c\ge m-1\ge 0$, what is the smallest real number $d(m,c)$ such that, if $M$ is a rank-$r$ $\PG(m-1,2)$-free binary geometry with $|M| \gt d(m,c) 2^r$, then $M$ has critical exponent $\le c$?

Govaerts and Storme’s Theorem shows that $d(m,m-1) = 1-\frac{11}{2^{m+2}}$. In particular, $d(2,1)= \frac{5}{16}$. Computing $d(2,c)$, for each $c\ge 2$, looks to be an interesting problem.

References

[AES74] B. Andrásfai, P. Erdös, V.T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974).

[BB66] R.C. Bose, R.C. Burton, A characterization of flat spaces in a finite geometry and the uniqueness of the Hamming and MacDonald codes, J. Combin. Theory 1 (1966).

[Beu80] A. Beutelspacher, Blocking sets and partial spreads in finite projective spaces, Geometriae Dedicata 9 (1980).

[BT] S. Brandt, S. Thomassé, Dense triangle-free graphs are four-colorable: A solution to the Erdös-Simonovits problem.

[ES73] P. Erdös, M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973).

[GN13] J. Geelen, P. Nelson, On minor-closed classes of matroids with exponential growth rate, Advances Appl. Math. 50 (2013).

[GS06] P. Govaerts, L. Storme, The classification of the smallest nontrivial blocking sets in $\PG(n,2)$, Journal of Combinatorial Theory, Series A 113 (2006).

[HS01] J.W.P. Hirschfeld, L. Storme, The packing problem in statistics, coding theory and finite projective spaces: update 2001.

[Jin95] G. Jin, Triangle-free four-chromatic graphs, Discrete Math. 145 (1995).

[Tur41] P. Turán, Eine extremalaufgabe aus der Graphentheorie, Mat. Fiz, Lapok 48, (1941).

Leave a Reply

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