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!

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 Form, of 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

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

A few days ago I was talking about 37ACCMCC in Perth. It was a great conference, and we all had a good time. If my vivid and evocative prose made you feel bad about missing out, never fear. You can always go next year! 38ACCMCC will be held at my own university, Victoria University of Wellington. The dates are Monday 1 December 2014 to Friday 5 December 2014. Matroids will be represented by Stefan van Zwam, who will be familiar to readers of this blog, and also by James Oxley, senior matroid statesman, and author of a book you may have come across.

The website for the conference is only basic at the moment, but functionality will be added when registration and accommodation become available. Keep on checking back. Hope to see you in NZ!