$\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!

I’ve been on the road: three Canadian provinces and six states (five American, one Australian) in the last two months. My body-clock has no idea what it should be set to, and this morning I found myself utterly befuddled when I woke up in my own bedroom for the first time in months — but the upside is that I’ve been to a couple of really enjoyable meetings.

Combinatorial Potlatch

The Combinatorial Potlatch is a British Columbian/Pacific North-West institution. The word Potlatch refers to a gift-giving festival practised by the indigenous inhabitants of the area, and it was chosen to reflect the informal and hospitable nature of the workshop. I really like the way the meeting is run: it lasts only one day, there are only two or three speakers, and the day ends in the pub. Nobody speaks more than once in the series, ensuring that new people to the area are given a chance to participate. Judging by this year’s meeting, there is also an emphasis on inviting early-career mathematicians. In fact I had the slightly unsettling experience of being the oldest of the speakers: the first time this has happened to me, but probably not the last (if I can be presumptuous enough to expect further invitations).

In its recent incarnation, the Potlatch is organised by Nancy Neudauer and Rob Beezer, both of whom I know from a short course on matroid theory that Nancy ran during the 2011 joint meeting of the AMS and MAA. Every year a university from the region is tapped to host the meeting, and in 2013 it was the turn of Victoria University, the namesake of my own institution. The name of this Victoria is slightly more obvious, as it resides in the town of Victoria, provincial capital of British Columbia, and largest urban area on Vancouver Island. I had been in Vancouver immediately before the meeting, so I caught the ferry, which dodges islands in the Juan De Fuca Strait.

The island is also beautiful. While I was there I got to see some spawning salmon:

Of course, you don’t get to spawn without breaking some fish:

All part of life’s cycle, but it does make for a fairly pungent atmosphere.

I enjoyed the two talks that I got to see at the Potlatch. Richard Hoshino gave an interesting and personal talk about some of his career choices; in particular, his decision to emphasise education and real-world optimisation over pure research that is unlikely to be appreciated or noticed by more than a handful. Speaking for myself, it doesn’t bother me too much that my research will only ever be read by specialists. I think it’s legitimate for artists and pure mathematicians alike to gain satisfaction from doing the best work they can, while letting the audience take care of itself — the number of people who appreciate a piece of work isn’t necessarily the best indication of its quality anyway. But I certainly understand that not everyone feels as I do.

Jérémie Lumbroso gave an attractive talk on an idea that I hadn’t encountered before: if we have a generating function that enumerates a class of combinatorial objects, then we can use that generating function to construct a parameterised random algorithm that will select one of those objects. The choice of parameter will influence the size of the object chosen by the algorithm. Therefore, if we want to randomly select a rooted binary tree embedded in the plane with 20 vertices (say), then we adjust our parameter so that the algorithm will deliver a tree of the right size with reasonable probability, and we let it run until it produces an output with 20 vertices. This process chooses trees of 20 vertices with uniform probability. Jérémie showed us the code that he used to implement the algorithm, and it was remarkably simple: just a couple of lines of Mathematica code.

37ACCMCC

Soon after the Potlatch, it was time for me to head to Perth for the 37th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing. Matroidunion.org’s own Irene Pivotto was a member of the organising committee, and Gordon Royle from SymOmega lead the committee. It was an extremely well-run meeting; so much so, in fact, that you can only feel sorry for the organiser of the 38th conference, given the high standards that he or she will have to live up to. (Expect to see more posts about 38ACCMCC sometime soon.)

I enjoyed many talks at the ACCMCC, so I will mention only the ones with significant amounts of matroid content. Nick Brettell spoke about an algorithm for constructing a $k$-tree of a matroid; Ben Clark talked about a project that myself and Stefan are involved in: the attempt to find excluded minors for the matroids representable over the partial field $\mathbb{H}_{5}$; Rong Chen talked about an inductive connectivity theorem for $k$-coherent matroids; Darryl Funk described work on the excluded minors for the class of frame matroids; Songbao Mo talked about a polymatroidal characterisation of abstract connectivity functions; Peter Nelson’s presentation covered some of the same material as his most recent post; Irene Pivotto spoke about some work she has done with Rong on a class of matroids arising from bias graphs; Michael Welsh described work on a conjecture of Steven Archer on maximum-sized golden-mean matroids. I think that covers everyone, so apologies if I have missed anyone.

The talks I gave at the two conferences were basically isomorphic (so apologies to the two people who were in the audience for both). In the first half I introduced matroids, and talked about excluded-minor characterizations, both exisiting and those still in progress. The second half was dedicated to work I have been doing with Mike Newman and Geoff Whittle on the impossibility of using matroid axioms to capture representability. Here are my slides.

Postscript

Attending these conferences made me think again about a small peeve of mine. I can’t understand the practice of abbreviating one’s own name to an initial when listing the authors of a theorem. You will no doubt know what I mean:

Theorem (M., Newman, Whittle — 2013)

instead of

Theorem (Mayhew, Newman, Whittle — 2013).

Can anyone tell me why we do this? It makes no sense to me. Slides usually have enough room to list names in full, so it can’t be a space constraint. Perhaps it comes from some sense of humility, as if we don’t want to lay too much of a claim to our own work lest we appear immodest? If that’s the case, then we seem to be saying that writing one’s own name above a theorem that we helped prove is an unbearable act of self-aggrandisement, and I can’t agree with that. I think it’s probably more likely that the custom just started years ago, and now people do it because it is what everyone does. But that’s not a good enough reason to continue a tradition. Unless somebody gives a masterful argument in favour of the practice in the comments, then I am going to write my own name in full on my slides, and I think others should do the same.