{"id":578,"date":"2013-12-23T09:00:02","date_gmt":"2013-12-23T14:00:02","guid":{"rendered":"http:\/\/matroidunion.org\/?p=578"},"modified":"2013-12-27T04:49:22","modified_gmt":"2013-12-27T09:49:22","slug":"the-bose-burton-theorem","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=578","title":{"rendered":"The Bose-Burton Theorem"},"content":{"rendered":"

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

Note: next week there will be no post. The Matroid Union will return on January 6 with a post by Stefan. Happy holidays!<\/em><\/p>\n

Guest post by Jim Geelen. <\/p>\n

A graph is called $H$-free <\/em> if it has no subgraph isomorphic to $H$. The Turán problem <\/em> 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 <\/em> (that is, simple binary matroids). A binary geometry is called $N$-free <\/em> if it has no restriction isomorphic to $N$. The Turán problem <\/em> 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. <\/p>\n

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. <\/p>\n

$K_t$-free graphs <\/h1>\n

We start with the classical result of Turán. <\/p>\n

The Turán graph <\/em> $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)$. <\/p>\n

Turán’s Theorem: <\/strong> 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)$.
\n<\/i> <\/p>\n

$\\PG(m-1,2)$-free geometries <\/h1>\n

The Bose-Burton geometry <\/em>, 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 <\/em> 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$. <\/p>\n

Bose-Burton Theorem: <\/strong> 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)$. <\/i> <\/p>\n

The result is easier to prove in the following form. <\/p>\n

Theorem: <\/strong> 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)$. <\/i> <\/p>\n

Proof. <\/strong> 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$<\/p>\n

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

Graphs near the threshold <\/h1>\n

The density <\/em> 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). <\/p>\n

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}$. <\/p>\n

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$. <\/p>\n

Theorem: <\/strong> 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. <\/i> <\/p>\n

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. <\/p>\n

Geometries near the threshold <\/h1>\n

The density <\/em> 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}$. <\/p>\n

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]. <\/p>\n

Theorem: <\/strong> 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$. <\/i> <\/p>\n

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. <\/p>\n

Triangle-free graphs <\/h1>\n

The following striking sequence of results on triangle-free graphs begs for an analogue in the context of binary geometries. <\/p>\n