Guest post by Jan Draisma, Eindhoven University of Technology.

I’d like to discuss some old and new developments on Rota’s basis conjecture.

Rota’s basis conjecture.
Let $V$ be an $n$-dimensional vector space over a field $K$, and for each $i=1,\ldots,n$ let $v_{i1},\ldots,v_{in}$ be a basis of $V$. Then there exist permutations $\pi_1,\ldots,\pi_n \in S_n$ such that for each $j\in [n]$ the transversal $v_{1,\pi_1(j)},v_{2,\pi_2(j)},\ldots,v_{n,\pi_n(j)}$ is a basis of $V$, as well.

I first learned about this conjecture in 2005 from the beautiful chapter Ten abandoned goldmines [Cra01] in a tribute to Gian-Carlo Rota. Ignorantly, I sat down on my balcony and thought, this must be easy… let’s identify $V$ with $K^n$ and introduce a variable $x_{ijk}$ for the $k$-th coordinate of $v_{ij}$. These are arranged in a cube whose horizontal slices are matrices with non-zero determinants. Let $\mathrm{hdet}$ denote the product of these horizontal determinants. For each choice $\pi (\pi_1,\ldots,\pi_n)$ let $\mathrm{vdet}_\pi$ be the product of the vertical determinants $\det(x_{i,\pi_i(j),k})_{i,k}$ for $j=1,\ldots,n$. Both $\mathrm{hdet}$ and $\mathrm{vdet}_\pi$ are degree-$n^2$ polynomials in the $x_{ijk}$, and the conjecture is equivalent (if $K$ is algebraically closed) to the statement that some power of $\mathrm{hdet}$ lies in the ideal generated by $\{\mathrm{vdet}_\pi \mid \pi \in S_n^n\}$. But they have the same degree, so perhaps $\mathrm{hdet}$ itself is already a linear combination of the $\mathrm{vdet}_\pi$? There is a natural guess for the coefficients: the polynomial \[ P=\sum_{\pi \in S_n^n} \mathrm{sign}(\pi_1) \cdots \mathrm{sign}(\pi_n) \mathrm{vdet}_\pi \] is multilinear in the $n^2$ vectors $v_{ij}$ and changes sign when you swap two vectors in the same row. There is only a one-dimensional space of such polynomials, and it is spanned by $\mathrm{hdet}$. So $P=c \cdot \mathrm{hdet}$ for some constant $c \in K$ and we’re done…oh, but wait a minute, let’s evaluate $c$. Each multilinear monomial in the $n^2$ vectors $v_{ij}$ is a product over all $(i,j)$ of a coordinate $x_{ijk}$ of $v_{ij}$ and can therefore be represented by an $n \times n$-matrix with entries $k \in [n]$. So for instance the monomial $m:=\prod_{i=1}^n (x_{i11} x_{i22} x_{i33} \cdots x_{inn})$ corresponds to the matrix with all rows equal to $1,2,\ldots,n$. The monomial $m$ appears in $\mathrm{vdet}_\pi$ if and only if, for each $j \in [n]$, the numbers $\pi_1(j),\ldots,\pi_n(j)$ are all distinct, i.e., if the array $(\pi_i(j))_{ij}$ is a Latin square (LS). The coefficient of $m$ in $P$ is then \[ \mathrm{sign}(\pi_1) \cdots \mathrm{sign} (\pi_n) \cdot \mathrm{sign}(\sigma_1) \cdots \mathrm{sign}(\sigma_n), \] where $\sigma_j:i \mapsto \pi_i(j)$ are the permutations given by the columns of the LS. Call an LS even if the coefficient above is $1$ and odd if it is $-1$. Then we have \[ c=\mathrm{ELS}(n)-\mathrm{OLS}(n) \] where $\mathrm{ELS}(n)$ is the number of even LS of order $n$ and $\mathrm{OLS}$ is the number of odd LS. Now if the characteristic of $K$ does not divide $c$, then we are done. Hmm, but why should $c$ even be non-zero?

Of course, I found out that the identity \[ P=(\mathrm{ELS}(n)-\mathrm{OLS}(n)) \mathrm{hdet} \] had been discovered long before me [Onn97]. For odd $n$ it is useless, since swapping the last two rows gives a sign-reversing involution on the set of LS, so that $c=0$. For even $n$, the non-zeroness of $\mathrm{ELS}(n)-\mathrm{OLS}(n)$ was a already famous conjecture due to Alon and Tarsi [AT92]. So I decided to read up on the history of these and related conjectures.

What led Rota and his student Rosa Huang to the basis conjecture was their work in invariant theory [HR94], and in his talk [Rot98] Rota expressed the opinion that new insights in invariant theory would be required to settle the conjecture. Infinitely many cases of the non-zeroness of $\mathrm{ELS}(n)-\mathrm{OLS}(n)$ were settled in [Dri97] (for primes plus one) and [Gly10] (for primes minus one). See also [Ber12] for an elementary proof of both results using Glynn’s determinantal identity. For odd dimensions, recent work by Aharoni and Kotlar [AK11] relates an odd-$n$ version of Alon and Tarsi’s conjecture to a weaker version of the basis conjecture.

Another line of research concerns the natural generalisation of the basis conjecture to arbitrary matroids. This turns out to be true for $ n=3$ [Cha95] and for n=4 [Che12] and for paving matroids [GH06]. For general matroids, the following weakening is proved in [GW07]: a $k \times n$-array of elements in a matroid whose rows are bases has $n$ disjoint independent transversals if $n > \binom{k+1}{2}$. A reduction from Rota’s conjecture to a conjecture concerning only three bases was established in [Cho10].

A third direction, which I recently explored with Eindhoven Master’s student Guus Bollen [BD13], concerns the following strengthening of the basis conjecture. Suppose that the rows of the array $(v_{ij})_{ij}$ are given to you sequentially, and that you have to fix $\pi_i$ immediately after receiving the $i$-th row, without knowledge of the remaining rows. Does such an online algorithm exist for producing $\pi_1,\ldots,\pi_n$ satisfying the requirement in the conjecture? We prove the following surprising dichotomy: for even $n$, the non-zeroness of $\mathrm{ELS}(n)-\mathrm{OLS}(n)$ in $K$ implies the existence of such an algorithm, while for odd $n$ any online algorithm can be forced to make an error.

This leads to the following question: does the online version make sense for general matroids? Well, yes, but it is easy to come up with counterexamples of format $n \times n$ for $n \geq 3$, even among linear matroids: for the online algorithm above it is essential that the algorithm gets the vectors as input, not just their linear dependencies. But what about $k \times n$-arrays for smaller $k$? It is quite conceivable that the following problem has an easy solution.

Problem
Determine the maximal value of $k$, as a function of $n$, such that the online version of the basis conjecture has a positive answer for $k \times n$-arrays in general matroids.

To conclude, here is a rather wild speculation related to Rota’s remark that new techniques in invariant theory are needed. Among the most powerful new tools in invariant theory are invariant Hilbert schemes [Ber08,Bri13]. They might play a role as follows. Suppose that $v=(v_{ij})_{ij}$ is a counterexample to the basis conjecture. Think of the $v_{ij}$ as points in projective space $\mathbb{P}V$, and assume that no two rows represent the same set of $n$ projective points. Then the orbit of $v$ under the semi-direct product $G$ of $S_n^n$ (for permutations within rows) with $S_n$ (for permutations of the rows) is a set of $(n!)^{n+1}$ points in $(\mathbb{P}V)^{(n^2)}$. This finite $G$-stable set of points in the ambient space $(\mathbb{P}V)^{(n^2)}$ with $G$-action corresponds to a single point in a suitable $G$-invariant Hilbert scheme. Applying invertible linear transformations of $V$ yields further points in the Hilbert scheme. The power of Hilbert schemes is that they also parameterise non-reduced sets, which arise, for instance, by allowing some or all of the points in the set to collide (think of a double root of a polynomial, which encodes not just a root but also a tangency). So one would like to phrase the property of being a counterexample as a closed condition on all points of the invariant Hilbert scheme, use a one-parameter group of basis transformations to degenerate the alleged counterexample to a point in the Hilbert scheme corresponding to a non-reduced counterexample (where all $(n!)^{n+1}$ points collide but the scheme encodes an interesting higher-order tangency structure), and then use $G$-module structure of the coordinate ring of the limit to show that it is, in fact, not a counterexample… but all of this is, for the time being, just science fiction!

[AK11] Ron Aharoni and Daniel Kotlar. A weak version of rota’s basis conjecture for odd dimensions. SIAM J. Discrete Math., 2011. To appear, preprint here.

[AT92] Noga Alon and Michael Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125-134, 1992.

[BD13] Guus P. Bollen and Jan Draisma. An online version of Rota’s basis conjecture. 2013. Preprint, available here.

[Ber12] Jochem Berndsen. Three problems in algebraic combinatorics. Master’s thesis, Eindhoven University of Technology, 2012. Available electronically at here.

[Bri13] José Bertin. The punctual Hilbert scheme, lecture notes of the 2008 Grenoble Summer school in mathematics, available here.

[Bri13] Michel Brion. Invariant Hilbert schemes, pages 63-118. Number 24 in Advanced Lectures in Mathematics. International Press, 2013.

[Cha95] Wendy Chan. An exchange property of matroid. Discrete Math., 146:299-302, 1995.

[Che12] Michael Sze-Yu Cheung. Computational proof of Rota’s basis conjecture for matroids of rank 4. See this page, 2012.

[Cho10] Chow, Timothy Y. Reduction of Rota’s basis conjecture to a problem on three bases. SIAM J. Discrete Math 23(1): 369–371, 2009.

[Cra01] H. Crapo. Ten abandoned gold mines. In Algebraic combinatorics and computer science. A tribute to Gian-Carlo Rota, pages 3-22. Milano: Springer, 2001.

[Dri97] Arthur A. Drisko. On the number of even and odd Latin squares of order $p+1$. Adv. Math., 128(1):20-35, 1997.

[GH06] Jim Geelen and Peter J. Humphries. Rota’s basis conjecture for paving matroids. SIAM J. Discrete Math., 20(4):1042-1045, 2006.

[Gly10] David G. Glynn. The conjectures of alon-tarsi and rota in dimension prime minus one. SIAM J. Discrete Math., 24(2):394-399, 2010.

[GW07] Jim Geelen and Kerri Webb. On Rota’s basis conjecture. SIAM J. Discrete Math., 21(3):802-804, 2007.

[HR94] Rosa Huang and Gian-Carlo Rota. On the relations of various conjectures on latin squares and straightening coefficients. Discrete Math., 128:225-236, 1994.

[Onn97] Shmuel Onn. A colorful determinantal identity, a conjecture of Rota, and Latin squares. Am. Math. Mon., 104(2):156-159, 1997.

[Rot98] Gian-Carlo Rota. Ten mathematics problems I will never solve. Mitt. Dtsch. Math.-Ver., 2:45-52, 1998.

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

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

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