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

Guest post by Jim Geelen.

$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\cC}{\mathcal{C}}$ $\newcommand{\bF}{\mathbb{F}}$

Anyone who has given significant consideration to the classes of frame matroids and lifted graphic matroids will have been struck by their similarities. The point of this posting is that these classes can be unified in a way that might have significant algorithmic implications. We also prove an amazing result (Theorem 3) concerning representations of matroids in the unified class.

Graphic matroids

The class of graphic matroids is very well understood; for example, the set of excluded minors is known and there is a polynomial-time algorithm for recognizing whether a matroid, given by its rank oracle, is graphic.

There are two key parts to the recognition algorithm. First one needs an algorithm for testing whether a given binary matroid is graphic; see, for example, [BC80]. Second one needs to check, for a given matroid $M$ and graph $G$, whether $M=M(G)$. This second part is solved by the following beautiful result due to Seymour [Sey81].

Theorem 1: Let $M$ be a matroid and let $G$ be a loopless $2$-connected graph with $E(G)=E(M)$. Then $M=M(G)$ if and only if $r(M)\le |V(G)|-1$ and, for each vertex $v$ of $G$, the set of edges incident with $v$ in $G$ forms a cocircuit of $M$.

Bias graphs

In the following three short sections, I will review the frame matroid and the lift matroid associated with a bias graph. These objects were introduced by Zaslavsky [Zas91] and were discussed in Irene Pivotto’s post on August 26.

Let $\cC$ be a set of circuits in a graph $G$. A theta in $G$ is loopless $2$-connected subgraph $H$ with $|E(H)| = |V(H)|+1$. Thus, a theta has two special vertices connected by three internally-disjoint paths, and such graphs have exactly three circuits. We say that $\mathcal C$ has the theta-property if there is no theta in $G$ having exactly two of its three circuits in $\cC$. The pair $(G,\cC)$ is called a bias graph if $\cC$ has the theta-property.

Frame matroids

The frame matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $FM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and for each component of $G[I]$ has at most one circuit.

Zaslavsky showed that a matroid $M$ is a frame matroid if and only if there is a matroid $M’$ and a basis $B$ of $M’$ such that $M$ is a restriction of $M’$ and for each element $e\in E(M’)-B$, the unique circuit of $B\cup\{e\}$ contains at most two elements of $B$.

Lifts of graphic matroids

The lift matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $LM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and $G[I]$ contains at most one circuit. Any matroid that is the lift matroid of a bias graph is called a lifted graphic matroid.

Zaslavsky showed that a matroid $M$ is a lifted graphic matroid if and only if there is a matroid $M’$ an element $e\in E(M’)$ such that $M’\del e = M$ and
$M’\con e$ is graphic.

Combining the classes

Let us call a graph $G$ a framework for a matroid $M$ if

• $E(M) = E(G)$,
• $G$ is connected,
• $r(M)\le |V(G)|$, and
• for each vertex $v$ of $G$, the set of edges incident with $v$ is a cocircuit of $M$.

We will call $M$ a framework matroid if it admits a framework representation.

The definition of a framework is motivated by Theorem 1; it has the appealing property that it is constructive. Given a matroid $M$, via a rank oracle, and a graph $G$ one can readily check (in polynomial time) whether or not $G$ is a framework for $M$. This constructive property is in contrast with the following conjectures.

Conjecture 1: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=FM(G,\cC)$.

Conjecture 2: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=LM(G,\cC)$.

I further believe that the recognition problem is intractable for both the class of frame matroids and the class of lifted graphic matroids. In contrast, I think that one can recognize framework matroids.

Conjecture 3: There is a polynomial-time algorithm that, given a matroid $M$ via its rank oracle, determines whether $M$ is a framework matroid.

Technical details

Let us call a graph $G$ a weak framework for a matroid $M$ if

• $E(M) = E(G)$,
• $r(M)\le |V(G)|$,
• for each vertex $v$ of $G$, the set of edges incident with $v$ is the union of a collection of cocircuits of $M$ and a set of loops of $M$, and
• each loop of $M$ is a loop of $G$.

This weakened notion behaves nicely with respect to our three classes.

• If $G$ is a graph, the $G$ is a weak framework for $M(G)$.
• If $M$ is the frame matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.
• If $M$ is the lift matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.

Lemma 1: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $H$ is a subgraph of $G$, then $H$ is a weak framework of $M| E(H)$.

Proof. Note that for any edge $e$ of $G$, $G-e$ is a weak framework of $M-e$. Now consider a vertex $v$ of $G$ and let $X$ denote the set of edges incident with $v$. If there is a nonloop edge $e$ of $G$ that is incident with $v$, then there is a cocircuit $C^*$ of $M$ such that $e\in C^*\subseteq X$. Then $r(E(G-v)) \le r(E(G)) – 1 \le |V(G)|-1 = |V(G-v)|$. Hence $G-v$ is a weak framework of $M\del X$. Now the result follows by deleting the vertices $V(G)-V(H)$, in an appropriately chosen order, and then deleting the edges in $E(G[V(H)]) – E(H)$. $\Box$

Lemma 2: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, then $r(M)\ge |V(G)|-1$ and equality holds if and only if $M$ is the cycle matroid of $G$.

Proof. Order the vertices of $G$ in the order $(v_1,v_2,\ldots,v_n)$ such that, for each $i\ge 2$, the vertex $v_i$ has a neighbour among $\{v_1,\ldots,v_{i-1}\}$. The sets $E(G[\{v_1,v_2,\ldots,v_n\}]),\, E(G[\{v_1,v_2,\ldots,v_n\}]),\,\ldots, \,E(G[\{v_1\}])$ have strictly decreasing rank in $M$, so $r(M)\ge |V(G)|-1$.

Equality clearly holds when $M=M(G)$. Conversely suppose that equality holds. A routine variation on the proof of Lemma 1 proves that, for each subgraph $H$ of $G$, we have $r(E(H)) \le |V(H)|-1$. Then, by the first part of the proof, for each connected subgraph $H$ of $G$ we have $r(E(H)) = |V(H)|-1$. In particular, if $H$ is a circuit of $G$, then $E(H)$ is a circuit of $M$, and, if $H$ is a tree of $G$, then $E(H)$ is independent in $M$. Thus $M = M(G)$. $\Box$

The following result is an easy application of Lemmas 1 and 2.

Lemma 3: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $M$ is $3$-connected, then $G$ is $2$-connected.

Lemma 4: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, $M$ is $3$-connected, and $|E(M)|\ge 4$, then $M$ is a framework matroid.

Proof. We may assume that among all connected weak frameworks for $M$ we have chosen $G$ with as many loops as possible. Since $M$ has no loops, if $G$ is not itself a framework of $M$, then there is a vertex $v$ of $G$ such that the set $X$ of edges incident with $v$ is the union of at least two distinct cocircuits of $G$. By Lemma 1 and the fact that $M$ is simple, there is at most one loop at $v$. Choose a cocircuit $C^*\subseteq X$ so that $X-C^*$ contains no loop of $G$. Now define $G’$ by replacing each edge $e=vw$ of $X-C^*$ with a loop at $w$. Note that $G’$ is a weak framework of $M$ and, since $G$ is $2$-connected, $G’$ is connected. However, this contradicts our choice of $G$ and that completes the proof.$\Box$

This proves that:

Theorem 2: The class of framework matroids contains all $3$-connected frame matroids and all $3$-connected lifted graphic matroids.

Represented matroids

A matrix with at most two nonzero nonzero entries in each column is called a frame matrix. Let $A_1$ and $A_2$ be matrices over a field $\bF$ with a common set $E$ of column indices. We say that $A_1$ and $A_2$ are row equivalent if $A_1$ can be obtained from $A_2$ by elementary row operations.

Problem 1: Given as input a matrix $A$, decide whether $A$ is row equivalent to a frame matrix.

Note that, if a matrix $A$ is row-equivalent to a frame matrix, then $M(A)$ is a frame matroid.

Conjecture 4: There is a polynomial-time algorithm that solves Problem 1.

We say that $A_1$ and $A_2$ are projectively equivalent if $A_1$ is row equivalent to a matrix $A_3$ that can be obtained from $A_2$ by column scaling. A signed incidence matrix is a frame matrix with entries in $\{0,\pm 1\}$ such that each column sums to zero. A lift of a matrix is a matrix obtained by appending a new row. A lifted signed-incidence matrix is a lift of a signed-incidence matrix.

Problem 2: Given as input a matrix $A$, decide whether $A$ is projectively equivalent to a lifted signed-incidence matrix.

Note that, if a matrix $A$ is projectively equivalent to a lifted signed-incidence matrix, then $M(A)$ is a lift of a graphic matroid.

Conjecture 5: There is a polynomial-time algorithm that solves Problem 2.

The amazing theorem

Let $A\in \bF^{V\times E}$ be a frame matrix with no all-zero column. The support of $A$ is the graph $G=(V,E)$ such that a vertex $v\in V$ is incident with an edge $e\in E$ if and only if the $(v,e)$-entry of $A$ is nonzero. If $A$ is a signed-incidence matrix with support $G$, then we say that $A$ is a signed incidence matrix of $G$.

The following remarkable fact came out of discussions with Bert Gerards and Geoff Whittle.

Theorem 3: Let $A$ be a matrix and let $M=M(A)$ be a framework matroid with framework $G$. Then either

• $A$ is projectively equivalent to a lift of the signed-incidence matrix of $G$, or
• $A$ is row equivalent to a frame matrix whose support is $G$.

Proof. By Lemma 2, we may assume that $r(M) = |V(G)|$. For each cocircuit $C$ of $M$ there is a vector $v$ in the row space of $A$ whose support is $C$. Therefore there is a frame matrix $A’$ whose support is $G$ and whose row space is contained in the row space of $A$. Now $G$ is a weak framework for $M(A’)$, so the rank of $A’$ is either $|V(G)|$ or $|V(G)|-1$. If $A’$ has rank $|V(G)|$, then $A$ is row equivalent to the frame matrix $A’$, as required. Thus we may assume that $A’$ has rank $|V(G)|-1$. Then, by Lemma 2, $M(A’)= M(G)$ and hence $A’$ is projectively equivalent to the signed incidence matrix of $G$. Finally, since the row space of $A’$ is contained in the row space of $A$ and $rank(A) = rank(A’)+1$, $A$ is row equivalent to a lift of $A’$. $\Box$

Theorem 3 some interesting consequences; the first of these is a striking converse to Theorem 2.

Corollary 1: For any field $\bF$, if $M$ is an $\bF$-representable framework matroid, then $M$ is either a frame matroid or a lifted graphic matroid.

Corollary 2: If $M$ is a $3$-connected matroid that has a representation by a frame matrix, then every representation of $M$ is either row equivalent to a frame matrix or is projectively equivalent to a lifted signed incidence matrix.

Corollary 3: If $M$ is a $3$-connected matroid that has a representation by a lifted signed incidence matrix, then every representation of $M$ is either projectively equivalent to a lifted signed incidence matrix or is row equivalent to a frame matrix.

Consider, for example, the matroid $R_{10}$. It is represented over GF$(3)$ by the “unsigned” incidence matrix of $K_5$. However, over GF$(2)$ it is represented by a lift of a signed incidence matrix of $K_5$.

References

[BC80] R.E. Bixby, W.H. Cunningham, Converting linear programs to network problems, Math. Oper. Res. 5 (1980), 321-357.
[Sey81] P.D. Seymour, Recognizing graphic matroids, Combinatorica 1 (1981), 75-78.
[Zas91] T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory, Ser. B 51 (1991), 46-72.