On a Cantor-Bernstein property of infinite matroids

Guest post by Attila Joó.

In this post we report an interesting property of infinite matroids that provides a common generalisation of the papers ‘A Cantor-Bernstein theorem for paths in graphs’ by Diestel and Thomassen [1] and ‘A Cantor-Bernstein-type theorem for spanning trees in infinite graphs’ by Erde, Gollin, Joó, Knappe, and Pitz [2]. This generalisation also leads to some new applications.

Let us reformulate the Cantor-Bernstein theorem in the language of graph theory:


Theorem (Cantor-Bernstein [3]): If $ G=(V_0,V_1;E) $ is a bipartite graph and matching $ I_i $ covers $ V_i $ for $ i\in \{ 0,1 \} $, then $ G $ admits a perfect matching.

Ore discovered the following generalisation of the Cantor-Bernstein theorem which is the extension of the Mendelsohn-Dulmage theorem to infinite graphs:

Theorem (Ore [4]): Let $ G=(V_0,V_1;E) $ be a bipartite graph and let $ I_0, I_1\subseteq E $ be matchings in $ G $. Then there exists a matching $ I $ such that $ V(I)\cap V_i\supseteq V(I_i)\cap V_i $ for $ i\in \{ 0,1 \} $.


Diestel and Thomassen [1] examined a more general graph theoretic setting in which disjoint paths are used to connect two vertex sets:

Theorem (Diestel and Thomassen [1]): Assume that $ G=(V,E) $ is a graph, $ V_0, V_1\subseteq V$ and $ \mathcal{P}_i $ is a system of disjoint $V_0V_1$-paths in $ G $ for $ i\in \{ 0,1 \} $. Then there exists a system of disjoint $ V_0V_1 $-paths $ \mathcal{P} $ with $ V(\mathcal{P})\cap V_i \supseteq V(\mathcal{P}_i)\cap V_i $ for $ i\in \{ 0,1 \} $.

In our paper [2] entitled ‘A Cantor-Bernstein-type theorem for spanning trees in infinite graphs’ we investigated if the existence of a $ \kappa $-packing and a $ \kappa $-covering by spanning trees implies the existence of a $ \kappa $-family of spanning trees which is both, i.e. a $ \kappa $-partition:

Theorem (Erde et al. [2]): Let $ G=(V,E) $ be a graph and let $ \kappa $ be a cardinal. If there are $ \kappa $ many pairwise edge-disjoint spanning trees in $ G $ and $ E $ can be covered by $ \kappa $ many spanning trees, then $ E $ can be partitioned into $ \kappa $ many spanning trees.

We believed that the connection between the two previous theorems above is only analogical but it turned out that the connection is actually stronger. Namely, both of them are special cases of a “Cantor-Bernstein theorem” of infinite matroids. To state this matroidal generalisation we fix some notation. We call a matroid (co)finitary if all of its (co)circuits are finite. Note that the cofinitary matroids are exactly the duals of the finitary ones. Let us denote the class of finitary and cofinitary matroids by $ \mathfrak{F} $ and $\mathfrak{F}^{*} $ respectively. Let $ \mathfrak{F}\oplus \mathfrak{F}^{*} $ be the class of matroids having only finitary and cofinitary components, equivalently that are the direct sums of a finitary and a cofinitary matroid (Bowler called them ‘simple matroids’ in the previous post). For a matroid class $ \mathfrak{C} $, let $ \mathfrak{C}(E) $ denote the set of matroids on edge set $ E $ that are in class $\mathfrak{C} $.

Theorem (J.): For $ i\in \{ 0,1 \} $, let $ M_i\in (\mathfrak{F}\oplus \mathfrak{F}^{*})(E) $ and $ F_i\subseteq E $. Then there exists an $ F\subseteq E $ such that $ \mathsf{span}_{M_i}(F)\supseteq F_i $ and $ \mathsf{span}_{M_i^{*}}(E\setminus F)\supseteq E\setminus F_{1-i} $ for $ i\in \{ 0,1 \} $.

The special case where $F_i$ are common independent sets and the matroids are finite is a theorem of Kundu and Lawler [5]. It is worth to mention that $\mathfrak{F}\oplus\mathfrak{F}^{*}$ cannot be replaced by the class of all matroids in the theorem above because the resulting statement fails under the Continuum Hypothesis. We do not know at this point if a counterexample can be found in set theory ZFC alone. It is also unclear if $\mathfrak{F}\oplus\mathfrak{F}^{*}$ can be replaced by some larger “well-behaved” class of matroids like the so called tame matroids. The latter class consists of those matroids in which the intersection of a circuit and a cocircuit is always finite. This class was intensively studied by Bowler, Carmesin and others. It was shown for example by Carmesin that the bases of a fixed tame matroid have the same size. The analogous statement for arbitrary matroids is independent of ZFC (the positive and negative direction of the independence was proved by Higgs and Bowler & Geschke [6] respectively).

In order to derive the mentioned theorem of Diestel and Thomassen [1] from the theorem above, one needs to choose $M_i$ to be the cycle matroid of the graph obtained by contracting $V_{1-i}$ in $G$ and let $F_i:= E(\mathcal{P}_{i})$. One can show that the set of all the $V_0V_1$-paths in $G[F]$ is suitable as $ \mathcal{P}.$ For the spanning tree partitioning result we need a “packing-covering-partitioning family version” of the previous theorem:

Theorem(J.): For $ i\in \Theta$, let $ M_i\in (\mathfrak{F}\oplus \mathfrak{F}^{*})(E) $ and $ P_i,R_i \subseteq E $ such that $ P_i\cap P_j=\varnothing $ for $ i\neq j$ and $ \bigcup_{i\in \Theta}R_i=E $. Then there are $ T_i\subseteq P_i\cup R_i $ for $ i\in \Theta $ forming a partition of $ E $ such that $ \mathsf{span}_{M_i}(T_i)\supseteq P_i $ and $\mathsf{span}_{M_i^{*}}(E\setminus T_i)\supseteq E\setminus R_i $.

This version can be obtained from the previous form in the same way as the Matroid Intersection Conjecture and the Packing-Covering Conjecture can be derived from each other (see the previous post by Bowler). The special case where $P_i$ and $R_i$ are assumed to be bases of $M_i$ is an earlier theorem by Erde et al. [7] and was conjectured by Bowler. By choosing all $M_i$ to be the cycle matroid of $G$, sets $P_i$ to be the (edge sets of) spanning trees forming a packing and the $R_i$ to be spanning trees forming a covering, the sets $T_i$ form the desired partition.

Finally, we mention two applications. According to an unpublished result of Bowler and Carmesin, for every compact graph-like space (introduced by Thomassen and Vella [8]) the edge sets corresponding to pseudo-cycles are the circuits of a cofinitary matroid. This makes it possible to extend the scope of the mentioned theorem of Diestel and Thomassen to compact graph-like spaces (using pseudo-arcs as a replacement of graph theoretic paths).

The other application corresponds to the Matroid Intersection Conjecture of Nash-Williams (discussed in the previous post by Bowler). Let $M_0, M_1 \in (\mathfrak{F}\oplus \mathfrak{F}^{*})(E) $ be fixed. For an $I\in \mathcal{I}_{M_0}\cap \mathcal{I}_{M_1} $ the following statements are known to be equivalent:

1. There is a partition $ E=E_0\sqcup E_1 $ such that $ I_i:=I\cap E_i $ spans $E_i $ in $M_i $ for $ i\in \{ 0,1 \} $.
2. $I$ is strongly maximal, i.e. $ \left|J\setminus I\right|\leq \left|I\setminus J\right| $ for every $ J\in \mathcal{I}_{M_0}\cap \mathcal{I}_{M_1} $.

If the matroids are finite (i.e. $E$ is finite), then ‘strongly maximal’ is equivalent with ‘of maximal size’ but in general strong maximality is a strictly stronger notion. The Matroid Intersection Conjecture claims the existence of a strongly maximal common independent set and is known to be true if $E$ is countable [11].

For $I, J \in \mathcal{I}_{M_0}\cap \mathcal{I}_{M_1} $ let $ J\trianglelefteq I $ iff $ J\subseteq \mathsf{span}_{M_0}(I)\cap \mathsf{span}_{M_1}(I) $. It is not too hard to see that if $E$ is finite, then the strongly maximal (i.e. maximal sized) common independent sets are exactly the $\trianglelefteq $-maximal ones ($I$ is $\trianglelefteq $-maximal iff $ I \trianglelefteq J $ implies $ J \trianglelefteq I $ for every $J\in \mathcal{I}_{M_0}\cap \mathcal{I}_{M_1} $). According to the second application, if $E$ is countable, then the set of the strongly maximal elements of $\mathcal{I}_{M_0}\cap \mathcal{I}_{M_1}$ is $\trianglelefteq $-cofinal in $\mathcal{I}_{M_0}\cap \mathcal{I}_{M_1}$, however, in contrast of the finite case it might be not even upward $\trianglelefteq $-closed in $\mathcal{I}_{M_0}\cap \mathcal{I}_{M_1}$.

[1] R. Diestel and C. Thomassen, A Cantor-Bernstein theorem for paths in graphs, The American Mathematical Monthly 113 (2006), no. 2, 161–166.
[2] J. Erde, J P. Gollin, A. Joó, P. Knappe, and M. Pitz, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs, Journal of Combinatorial Theory, Series B 149 (2021), 16–22.
[3] G. Cantor, Mitteilungen zur lehre vom transfiniten, Zeitschrift für Philosophie und philosophische Kritik 91 (1987), 81–125.
[4] O. Ore, The theory of graphs, American Mathematical Society, 1962.
[5] S. Kundu and E. L Lawler, A matroid generalization of a theorem of Mendelsohn and Dulmage, Discrete Mathematics 4 (1973), no. 2, 159–163.
[6] N. Bowler and S. Geschke, Self-dual uniform matroids on infinite sets, Proceedings of the American Mathematical Society 144 (2016), no. 2, 459–471.
[7] J. Erde, J. P. Gollin, A. Joó, P. Knappe, and M. Pitz, Base partition for mixed families of finitary and cofinitary matroids, Combinatorica 41 (2021), no. 1, 31–52.
[8] C. Thomassen and A. Vella, Graph-like continua, augmenting arcs, and Menger’s theorem, Combinatorica 28 (2008), no. 5, 595–623.
[9] R. Aharoni and R. Ziv, The intersection of two infinite matroids, Journal of the London Mathematical Society 58 (1998), no. 03, 513–525.
[10] A. Joó, Proof of Nash-Williams’ intersection conjecture for countable matroids, Advances in Mathematics 380 (2021), 107608.
[11] A. Joó, On the Packing/Covering Conjecture of infinite matroids (2021). https://arxiv.org/abs/2103.14881
[12] N. Bowler, Infinite matroids, Habilitation Thesis, 2014. https://www.math.uni-hamburg.de/spag/dm/papers/Bowler_Habil.pdf
[13] A. Joó, On a linking property of infinite matroids (2021). https://arxiv.org/abs/2009.08439.


The Sylvester-Gallai Theorem

Guest contributor: Jim Geelen

In this post we consider some problems related to the following classical result (posed by Sylvester in 1893 and proved by Gallai in 1944).

Sylvester-Gallai Theorem: Given any finite set of points in the real plane, not all on a line, we can find a line in the plane that contains exactly two of them.

That is, in matroid-thoretic language, every simple, rank-$3$, real-representable matroid contains a $2$-point line. Geometers have considered a number of related problems, but there does not seem to have been much work on this in the matroid theory community. I’ve not thought about these questions much, and have not done a thorough literature review, but I’m just going to put the problems out there for discussion. I’ll start with a brief discussion about what is known for real-representable, complex-representable, and binary matroids.

In geometry, an ordinary line is a line with exactly two points. This has an obvious generalization to higher rank flats, however, the term “ordinary flat” is used to describe a different, less natural, generalization of ordinary lines, which we define later. So, following conventions in geometry, we will call a flat in a matroid elementary if it is an independent set.

Does every simple real-representable matroid with rank at lest $4$ contain an elementary plane? This was answered in the negative by Motzkin in 1951 who presented two counterexamples; the first being the direct sum of two lines. The second example is more subtle; take $5$ planes in $\mathbb R^3$ in general position; any three of the planes intersect in a point, and these 10 points give a counterexample.  These were thought to be the only examples, until 1971, when Bonnice and Kelly presented an infinite family. Later, Hansen added to the list of known counterexamples.

Problem 1: Classify the simple rank-$4$ real-representable matroids that do not have an elementary plane.

Given the list of known examples, that problem is likely to be quite challenging.

Geometers have a non-trivial generalization of the Sylvester-Gallai Theorem, given below. A flat $F$ of a matroid $M$ is ordinary if $M|F$ has a coloop. Thus, in a simple matroid, elementary lines and ordinary lines are the same thing.

Hansen’s Theorem: For each $r\ge 3$, every simple rank-$r$ real-representable matroid contains an ordinary hyperplane.

The definition of ordinary flats seems a bit contrived, but the result does have interesting consequences.

Corollary 2: Every simple rank-5 real-representable matroid has an elementary plane.

Proof: Suppose that $M$ is a simple rank $5$ real-representable matroid. By Hansen’s Theorem there is an ordinary hyperplane $H$ in $M$. By definition, $H=P\cup \{e\}$ for some plane $P$ and element $\{e\}$. By the Sylvester-Gallai Theorem, $P$ contains an elementary line $\{f,g\}$. Now $\{e,f,g\}$ is an elementary plane.$\Box$

Moreover, the same idea easily generalizes to higher-dimensions.

Corollary 3: For each $k\ge 2$ and $r\ge 2k-1$, if $M$ is a simple rank-$r$ real-representable matroid, then $M$ has an elementary rank-$k$ flat.

Since the direct-sum of $k-1$ triangles does not contain an elementary rank=$k$ flat, this bound is best possible.

Complex-representable matroids

It is easy to construct simple rank-$3$ matroids with no ordinary lines; projective planes and affine planes (over fields of size at least $3$) give examples. It is not as easy to come up with examples that are representable over the complex numbers, however, the ternary affine plane is complex representable. There are, in fact, infinitely many examples known in rank-$3$, but the list of known examples is believed to be complete. Increasing the rank to $4$ yields an ordinary line.

Theorem [Kelly, 1986]: Every simple complex-representable matroid with rank at least $4$ contains an ordinary line.

It is natural to wonder whether Corollary 3 extends to complex-representable matroids. I really like this conjecture, but it is hard to imaging that it is new.

Conjecture 4: For each positive integer $k$ there is an integer $R$, such that, if  $M$ is a simple complex-representable matroid with rank at least $R$, then $M$ contains an elementary rank-$k$ flat.

Binary matroids

I was led to these problems by results on binary matroids that I came across in Kazuhiro Nomoto’s Ph.D thesis. In particular, Peter Nelson and Kazuhiro Nomoto characterized the simple binary matroids with no elementary plane. Their theorem statement is not particularly complicated, so I will state it, but it is not directly relavent to any of the conjectures, so I will not go into any detail.

Theorem [Nelson, Nomoto]: A simple binary matroid $M$  has no elementary plane if and only if it can be obtained via lift-joins from:

  • the direct sums of two projective geometries,
  • even-plane matroids, and
  • complements of triangle-free binary matroids,

Here a matroid is even-plane if each of its planes have an even number of points; these matroids have an unexpected description as roots of quadtratic equations. This class is particularly interesting as it has unbounded critical number. You might want to look at the the paper for a definition of a lift-join of simple binary matroids $N_1$ and $N_2$, but here is a cryptic definition; it is the unique maximal simple binary matroid $M$ spanned by the direct sum of $N_1$ and $N_2$ such that $M/E(N_2)$ is loopless and simplifies to $N_1$.

Since this result is already quite complicated, it would be presumably very hard to characterize the simple binary matroids with no elementary flat of rank $4$. For other finite fields $\mathbb F$ and integers $k\ge 2$, one could try to classify the simple $\mathbb F$-representable matroids with no elementary rank-$k$ flat. The only other instance of this problem that looks approachable is:

Exercise 5: Characterize the simple ternary matroids with no elementary line.

Hint: If you consider a simple ternary matroid as a restriction of a ternary projective geometry then the matroid has an elementary line if and only if its complement does. Show that if there is no elementary line then the matroid and its complement cannot both be spanning.

Matroids in general

The class of matroids with no ordinary line looks extremely complicated, but it would be nice to have some general Ramsey-theoretic tools for addressing Sylvester-Gallai-type problems. For example:

Conjecture 6: For any integer $k\ge 1$ there is an integer $R$ such that if $M$ is a simple matroid with rank at least $R$ then there is a rank-$k$ flat in $M$ such that either $M|F$ has no ordinary lines, or every line in $M|F$ is ordinary.

I don’t know whether I particularly believe this conjecture; it may be the case that $R$ may also depend on the maximum line-length.

Claim: Conjecture 6 implies Conjecture 4.

Proof. Consider the smallest integer $k$ such that Conjecture 3 fails. By Hansen’s Theorem, $k\ge 3$. Consider a simple complex-representable matroid $M$ with huge rank but with no elementary rank-$k$ flats. If Conjecture 5 were true we could find a large-rank flat $F$ in which all of the lines are ordinary. Now, for any $e\in F$, by induction $(M|F)/e$ has a rank-$(k-1)$ elementary flat $F’$. Then $F’\cup\{e\}$ is an elementary rank-$k$ flat in $M$. $\Box$

I will say that a class $\mathcal M$ of matroids satisfies the $k$-Sylvester Property if every simple matroid in $\mathcal M$ with sufficiently large rank contains an elementary rank-$k$ flat.  Note that if $\mathcal M$ does not satisfy the $k$-Sylvester Property, then $\mathcal M$ doe not satisfy the $k’$-sylvester Property for any $k’\ge k$. Using the proof idea from the previous claim, Conjecture 6 also implies:

Conjecture 7:  If $\mathcal M$ is a minor-closed class of matroids that satisfies the $2$-Sylvester property, then $\mathcal M$ satisfies the $k’$-Sylvester property for all $k’\ge 2$.

The following weakening of Conjecture 6 would already imply Conjecture 7.

Conjecture 8: For any integer $k\ge 1$ there is an integer $R$ such that if $M$ is a simple matroid with rank at least $R$ then there is a rank-$k$ flat in $M$ such that either there is a point in $M|F$ that is only on ordinary lines, or no line in $M|F$ is ordinary.

Elementary planes in triangle-free matroids

If $M$ is a triangle-free matroid with no elementary plane, then, for each element $e$ of $M$, the matroid $M/ e$ is simple and has no ordinary line. So results about ordinary lines can be lifted to give results about triangle-free matroids with no ordinary plane. For example, the Sylvester-Gallai Theorem implies that:

Theorem 9: If $M$ is a simple, triangle-free real-representable matroid with rank at least $4$, then $M$ has an elementary plane.

This result is implied by Hansen’s Theorem, but the proof of Hansen’s Theorem is considerably harder.

The next result follows from Kelly’s Theorem.

Theorem10: If $M$ is a simple, triangle-free complex-representable matroid with rank at least $5$, then $M$ has an elementary plane.

Projective geometries are the only simple binary matroids with no ordinary lines. Affine geometries are the only triangle-free, binary, single-element coextensions of binary projective geometries. Therefore:

Theorem [Nelson, Nomoto]: The only simple, triangle-free binary matroids with no elementary plane are the binary affine geometries.

To borrow a nice turn-of-phrase from Joseph Kung, the following conjecture reflects my current state of ignorance.

Conjecture 11: For any finite field $\mathbb F$ with odd characteristic, if $M$ is a simple, triangle-free $\mathbb F$-representable matroid with sufficiently large rank, then $M$ has an elementary plane.

Something much stronger may well hold:

Conjecture 12: For any finite field $\mathbb F$ with odd characteristic and integer $k\ge 3$, if $M$ is a simple, triangle-free $\mathbb F$-representable matroid with sufficiently large rank, then $M$ has an elementary rank-$k$ flat.

Higher girth

A matroid is simple and triangle-free if and only if it has girth at least $4$. If $e$ is an element in a matroid $M$ with girth $g$ and with no elementary rank-$k$ flat, then $M/e$ has girth $\ge g-1$ and has no elementary flat of rank $k-1$. Again this gives us an inductive tool.

Lemma: Every binary matroid with girth $\ge 5$ and rank $\ge 5$ contains an elementary rank-4 flat.

Proof. It suffices to prove the result when the rank and girth are both equal to $5$. Consider a binary matroid $M$ with rank and girth both $5$. Suppose that $M$ has no elementary rank-$4$ flat. For any element $e$ of $M$, the matroid $M/e$ is a simple, rank-$4$ triangle-free binary matroid with no elementary plane; therefore $M/e$ is isomorphic to the binary affine cube AG$(3,2)$. The binary affine cube is also known as the rank-$4$ binary spike, which is self-dual. Therefore $M^*$ is the unique binary single-element extension of the binary affine cube, which is the rank-$4$ binary spike with tip. However, this contradicts the fact that $M$ has girth $5$. $\Box$

Now an easy induction gives:

Theorem 13: For each $k\ge 4$, if $M$ is a binary matroid with rank and girth both at least $k+1$, then $M$ has an elementary rank-$k$ flat.

In fact, we can keep the girth at $5$ if we increase the rank.

Theorem 14: For each $k\ge 4$, if $M$ is a binary matroid  girth at least $5$ and with sufficiently large rank, then $M$ has an elementary rank-$k$ flat.

Proof. Fix a basis $B$, and for each element $e$ outside $B$ let $C_e$ be the unique circuit in $B\cup \{e\}$. We think of $C_e-\{e\}$ as a “hyper-edge” on the vertex set $B$ and apply the hypergraph Ramsey Theorem to get a $k$-element set $I\subseteq B$ such that, for each $t\in\{1,\ldots,k\}$, either all or none of the $t$-element subsets of $I$ are hyper-edges. We may assume that $I$ is not an elementary flat and hence there exists $t\in\{1,\ldots,k\}$ such that all of the $t$-element sets are hyperedges. Then there are two hyperedges whose symmetric difference has size two and hence $M$ has a circuit of size $4$.$\Box$

While it seems a bit wild, maybe we don’t even need representability.

Conjecture 15: For each $k\ge 4$, if $M$ is a matroid  with girth at least $5$ and with sufficiently large rank, then $M$ has an elementary rank-$k$ flat.

If you are not struck by this conjecture, read it again.

While writing this I benefitted from discussions with Nick Brettell, Rutger Campbell, James Davies, Matt Kroeker, Peter Nelson, and Geoff Whittle.

References

 

Matroids on graphs in applied algebraic geometry

Guest post by Daniel Irving Bernstein. Click here for the pdf version.

Many questions in applied algebraic geometry boil down to asking which polynomial functions within some family are generically finite-to-one. When the family consists of the coordinate projections of an irreducible variety, matroids arise. Two particular applications that have driven much research include matrix completion and rigidity theory. The ground sets of the matroids that appear therein are the edge sets of graphs.

Low rank matrix completion.

In a low-rank matrix completion problem, one is given access to a subset of entries of a matrix, and hopes to fill in the missing entries in a way that minimizes rank, or that achieves a particular low rank. For example, given any partial matrix of the following form

$$\begin{pmatrix}
a & b \\
c & \cdot
\end{pmatrix},$$

one can fill in the missing entry so that the resulting matrix has rank one. Namely, plug in $\frac{bc}{a}$ . Of course, this won’t work if $a=0$, but we can safely ignore this issue, and similar ones, by working over $\mathbb{C}$ and invoking a genericity assumption on the visible entries. In this setup, whether or not a particular partial matrix can be completed to a particular rank $r$ depends only on which entries are observed, and not their actual values. Thus, one can ask: given an integer $r \ge1$ and a subset E of entries of an $m\times n$ matrix – which is naturally encoded by the bipartite graph $([m],[n],E)$, see the figure below – can the resulting partial matrices be completed to rank $r$? The subsets of entries, i.e. bipartite graphs, for which the answer to this question is “yes” form the independent sets of a matroid. When $r=1$, this is the graphic matroid of the complete bipartite graph. When $r=2$, the independent sets of this matroid consist of all bipartite graphs that admit an edge two-coloring with no monochromatic cycle, nor any cycle whose edge colors alternate. More on this later.

The subset of known entries of the matrix to the left correspond to the graph on the right. If $a,b,c,d,e,f$ are sufficiently generic, then the partial matrix can be completed to rank two, but not rank one.

 

Rigidity Theory

If one were to physically build a graph $G$ in $d$-dimensional space, using rigid struts for the edges, and universal joints for the vertices (i.e. joints that the struts can move freely around) would the resulting structure be rigid, or flexible? Consider, for example, the four-cycle. If we build it in the plane as a square, then the resulting structure is flexible, since we can deform the square into a rhombus without stretching, compressing, or breaking any of the edges — see the figure below. However, if we add a chord to the four-cycle, then it becomes rigid in the plane.

The four-cycle is not rigid in the plane, but becomes rigid after adding a chord.

Whether or not a graph is rigid in $d$-dimensional space depends not only on the combinatorics of the graph, but also on the specific positions we place the vertices. For example, we can build the four-cycle in the plane so that it becomes rigid by placing all four vertices on a line. However, just as in the matrix completion example, we can safely ignore such issues by invoking a genericity assumption. Then, every graph will either be rigid or flexible in $d$-dimensional space, and we can ask to characterize those that are rigid. Moreover, the graphs on a fixed number of vertices that are rigid in $d$-dimensional space form the spanning sets of a matroid. When $d=1$, this is the graphic matroid of the complete graph (see if you can convince yourself of this). When $d=2$, the independent sets of this matroid consist of graphs such that every subgraph on $k$ vertices has at most $2k-3$ edges. More on this later.

Matroids from varieties

We will now describe how the two aforementioned matroids arise from the same construction from algebraic geometry.

A variety will refer to a subset of a finite-dimensional vector space that is defined by the simultaneous vanishing of a system of polynomial equations. We will be particularly concerned with irreducible varieties, which are varieties that cannot be expressed as a union of two proper subsets which are themselves varieties.

Let $E$ be a finite set, let $\mathbb{F}$ be a field, and let $\mathbb{F}^E$ denote the $\mathbb{F}$-vector space whose coordinates are indexed by elements of $E$. Each subset $S\subseteq E$ defines a coordinate projection $\pi_S:\mathbb{F}^E\rightarrow \mathbb{F}^S$. Given a variety $V$, the dimension of the image of $V$ under these coordinate projections gives us an integer valued set function
\[
\rho_V: 2^E \rightarrow \mathbb{N} \qquad {\rm given \ by} \qquad S\mapsto \dim(\pi_S(V)).
\] I claim that when $V$ is irreducible, $\rho_V$ is the rank function of a matroid. This matroid will be denoted by $\mathcal{M}(V)$, and it is known as the algebraic matroid of $V$.

I will briefly explain why $\mathcal{M}(V)$ is a matroid when $V$ is irreducible in the case that $\mathbb{F}$ is an uncountable field of characteristic zero (e.g. $\mathbb{R}$ or $\mathbb{C}$). First consider the case that $V$ is a linear space. Then, $V$ is an irreducible variety that can be obtained as the row-span of some matrix $A$ whose columns are indexed by $E$. Letting $A_S$ denote the column-submatrix of $A$ obtained by restricting to the columns indexed by $S\subseteq E$, we see that $\pi_S(V)$ is the row-span of $A_S$ and thus $\rho_V(S) = \dim(\pi_S(V)) = {\rm rank}(A_S)$. So $\rho_V$ is the rank function of the column-matroid of $A$. If $V$ is an arbitrary irreducible variety, then since $\mathbb{F}$ is an uncountable field of characteristic zero, it follows from some basic algebraic geometry that $\rho_V = \rho_L$ where $L$ is the tangent space to $V$ at a generic1 point. Translating $L$ so that it contains the origin gives us a linear space $L’$ such that $\rho_L = \rho_{L’}$. It now follows from the linear case that $\rho_V$ is the rank function of a matroid. Note that our proof implies that any matroid of the form $\mathcal{M}(V)$ is representable over $\mathbb{F}$ when $\mathbb{F}$ is uncountable of characteristic zero (this is no longer true for $\mathbb{Q}$ nor fields of prime characteristic [4]).

Some readers might be more familiar with a seemingly different definition of algebraic matroid. Namely, if $\mathbb{K}$ is a field extension of $\mathbb{F}$ and $E \subseteq \mathbb{K}$ is finite, then the subsets of $E$ that are algebraically independent over $\mathbb{F}$ form the independent subsets of a matroid. Matroids arising in this way are said to be algebraic matroids (over $\mathbb{F}$). There is no conflict in terminology here, and this stems from the fact that for any variety $W\subseteq \mathbb{F}^k$, the dimension of $W$ is defined to be the transcendence degree over $\mathbb{F}$ of the fraction field of $\mathbb{F}[x_1,\dots,x_k]/I$, where $I$ is the ideal of polynomials that vanish on $W$. When $\mathbb{F} = \mathbb{R}$ or $\mathbb{C}$, this definition is equivalent to the more intuitive notion of dimension from differential geometry, i.e. the dimension of a tangent space at a smooth point (and I will not discuss this further since the proof is quite deep, and requires a good bit of commutative algebra).

Determinantal varieties and matrix completion

Let ${\rm M}(m\times n,r) \subseteq \mathbb{C}^{m\times n}$ denote the set of $m\times n$ complex matrices of rank at most $r$. Since a matrix has rank $r$ or less if and only if all $(r+1)\times(r+1)$ submatrices have zero determinant, ${\rm M}(m\times n,r)$ is a variety. Moreover, it is irreducible so we can talk about its algebraic matroid. The ground set of this matroid is the set of entries of an $m\times n$ matrix, which we identify with the edge set of the complete bipartite graph $K_{m,n}$. Subsets of the ground set can therefore be described as bipartite graphs on partite sets of size $m$ and $n$.

Given a bipartite graph $G$, let $\mathbb{C}^G$ denote the vector space whose coordinates are indexed by edges of $G$, and let $\Omega_G:\mathbb{C}^{m\times n}\rightarrow \mathbb{C}^G$ be the map that projects a matrix $M$ onto its entries corresponding to the edges of $G$. Elements of $\mathbb{C}^G$ are called $G$-partial matrices. Given a $G$-partial matrix $A$, elements of $\Omega_G^{-1}(A)$ are called completions of $A$. A fundamental problem in low-rank matrix completion is to determine whether a given partial matrix $A \in \mathbb{C}^{G}$ has a completion to a particular rank. The following proposition tells us that assuming $A$ is generic, whether or not $A$ can be completed to rank $r$ depends only on $G$.

Proposition. Let $G = ([m],[n],E)$ be a bipartite graph and let $A \in \mathbb{C}^G$ be a $G$-partial matrix. If $A$ is generic, then $A$ has a completion to rank $r$ if and only if $G$ is independent in the algebraic matroid $\mathcal{M}({\rm M}(m\times n,r))$.

proof. Given any irreducible variety $V \subseteq \mathbb{C}^E$, $S\subseteq E$ is independent in $\mathcal{M}(V)$ if and only if $\dim(\pi_S(V)) = |S|$. This means that the set $\{x \in \mathbb{C}^S : x \notin \pi_S(V)\}$ is contained in a subvariety of $\mathbb{C}^{S}$, and in particular, has dimension strictly less than $|S|$. Thus given any generic $x \in \mathbb{C}^S$, there exists $y \in V$ such that $\pi_S(y) = x$. The proposition is now the special case where $V = {\rm M}(m\times n,r)$. ◊

The above proposition motivates the following general problem: for each positive integer $r$, give a combinatorial description of the (independent sets of) the matroid $\mathcal{M}({\rm M}(m\times n,r))$. This is open in all cases aside from $r=1$ and $r=2$. For $r=1$, it is relatively easy to show that $\mathcal{M}({\rm M}(m\times n,1))$ is the graphic matroid of $K_{m,n}$; we do this below.

Proposition. The matroid $\mathcal{M}({\rm M}(m\times n,1))$ is the graphic matroid of $K_{m,n}$. In other words, a bipartite graph $G = ([m],[n],E)$ is independent in $\mathcal{M}({\rm M}(m\times n,1))$ if and only if $G$ is a forest.

proof. Assume $G$ has no cycles. Let $X$ be a generic $G$-partial matrix. By the previous proposition, it suffices to show that $X$ can be completed to a rank-one matrix. Let $G’$ be obtained from $G$ by removing a vertex of degree zero or one; without loss of generality, assume it was the row-vertex $m$. Let $X’$ be the $G’$-partial matrix obtained from $X$ by removing the last row. By induction, $X’$ can be completed to a rank-one matrix $Y$. If the degree of $m$ was zero, then we can further complete $X$ to a rank-one matrix by plugging in zeros for the entries in the last row. If the degree of $m$ was $1$, then assuming the unique known entry of the $m^{\rm th}$ row of $X$ is in the first column, then multiply the $(m-1)^{\rm th}$ row of $Y$ by $X_{m,1}/Y_{m-1,1}$ and adjoining it to $Y$ gives a rank-one completion of $X$.

Now assume $G$ has a cycle $x_1,x_2,\dots,x_{2k}$ ($G$ is bipartite, so the cycle must have even length). Then $\pi_G({\rm M}(m\times n,1))$ must satisfy the equation $$x_1x_3\cdots x_{2k-1} = x_2x_4\cdots x_{2k}.$$ In particular, $\pi_G({\rm M}(m\times n,1))$ has dimension less than the number of edges of $G$. ◊

The characterization of $\mathcal{M}({\rm M}(m\times n,2))$ is more complicated. I will state it below; the interested reader is invited to read my paper [1] for the proof, which uses tropical geometry.

Theorem. Let $G = ([m],[n],E)$ be a bipartite graph. Then $G$ is independent in $\mathcal{M}({\rm M}(m\times n,2))$ if and only if there exists a two-coloring of the edges of $G$ with no monochromatic cycle, and no cycle whose edge-colors alternate.

Cayley-Menger varieties and rigidity theory

Consider the function $\phi_n^d:(\mathbb{R}^{d})^n\rightarrow \mathbb{R}^{\binom{n}{2}}$ that sends a configuration of $n$ points in $d$-dimensional space to their vector of squared pairwise distances. For example, if $d = 2$, this map would send the $n$ points $(x_1,y_1),\dots,(x_n,y_n)$ to the vector $$((x_i-x_j)^2 + (y_i-y_j)^2)_{1\le i < j \le n}.$$ The image of $\phi_n^d$ is subset of $\mathbb{R}^{\binom{n}{2}}$, and taking its Zariski closure in $\mathbb{C}^{\binom{n}{2}}$ (i.e. the smallest variety in $\mathbb{C}^{\binom{n}{2}}$ containing it) yields an irreducible variety ${\rm CM}_n^d$ called the Cayley-Menger variety of $n$ points in $\mathbb{R}^d$ (and yes, this is the Menger of Menger’s theorem). We can identify the coordinate indices of $\mathbb{C}^{\binom{n}{2}}$, i.e. the ground set of the matroid $\mathcal{M}({\rm CM}_n^d)$, with the edges of the complete graph $K_n$.

Proposition. A graph $G$ is spanning in $\mathcal{M}({\rm CM}_n^d)$ if and only if it is rigid in $d$-dimensional space.

proof sketch. Given any varieties $V$ and $W$ and any polynomial map $f: V\rightarrow W$, the following relationship holds for generic $x \in V$
\[
\dim(V) = \dim(f(V)) + \dim(f^{-1}(f(x))).
\] When $\dim(V) = \dim(f(V))$, this implies $\dim(f^{-1}(f(x))) = 0$ and since $\dim(f^{-1}(f(x))$ is a variety, this is equivalent to $\dim(f^{-1}(f(x))$ being a finite set. In particular, if $V \subseteq \mathbb{C}^E$ then $S \subseteq E$ is spanning in $\mathcal{M}(V)$ if and only if $\pi_S^{-1}(\pi_S(x)) \cap V$ is a finite set. So it remains to see that $G$ is rigid if and only if $\pi_G^{-1}(\pi_G(x)) \cap {\rm CM}_n^d$ is finite for generic $x \in {\rm CM}_n^d$. 

We now need to be more formal in our definition of rigidity. Suppose we build a graph $G$ in $\mathbb{R}^d$ by putting the vertices at points $p^{(1)},\dots,p^{(n)}$. A (nontrivial) \emph{flex} of $G$ is a curve in the space of configuration of $n$ points in $\mathbb{R}^d$, i.e. a function ${\bf p}:[0,1]\rightarrow (\mathbb{R}^d)^n$, such that

  1. the curve starts at the original configuration, i.e. ${\bf p}(0) = (p^{(1)},\dots,p^{(n)})$
  2. all configurations along the curve preserve edge lengths, i.e. for each $t \in [0,1]$ and edge $\{i,j\}$ of $G$, $\|{\bf p}(t)^{(i)}-{\bf p}(t)^{(j)}\|^2 = \|{\bf p}(0)^{(i)}-{\bf p}(0)^{(j)}\|^2$, and
  3. somewhere along the curve, the framework on $G$ actually gets deformed, i.e. for some $t \in [0,1]$ and some non-edge $\{i,j\}$ of $G$, $\|{\bf p}(t)^{(i)}-{\bf p}(t)^{(j)}\|^2 \neq \|{\bf p}(0)^{(i)}-{\bf p}(0)^{(j)}\|^2$.

This formalizes our intuitive notion of what it would mean to deform our particular construction of a graph. A graph is then (generically) rigid if for any generic point configuration $p^{(1)},\dots,p^{(n)}$, the corresponding framework on $G$ does not have any flex.

To see that the absence of a flex of $G$ is equivalent to the statement that $\pi_G^{-1}(\pi_G(x)) \cap {\rm CM}_n^d$ is generically finite, first note that if ${\bf p}:[0,1]\rightarrow (\mathbb{R}^d)^n$ is a curve satisfying the second condition required for ${\bf p}$ to be a flex of $G$, then $\pi_G\circ \phi_n^d \circ {\bf p}([0,1])$ is a single point $y$ in $\pi_G({\rm CM}_n^d)$, and $\pi_G^{-1}(y)\cap {\rm CM}_n^d$ contains $\phi_n^d \circ {\bf p}([0,1])$. The curve ${\bf p}$ additionally satisfies the third condition if and only if $\phi_n^d \circ {\bf p}([0,1])$ is one-dimensional, thus exhibiting infinitely many points in $\pi_G^{-1}(\pi_G(x)) \cap {\rm CM}_n^d$ for some $x \in \pi_G^{-1}(y) \cap {\rm CM}_n^d$. Conversely, since $\pi_G^{-1}(\pi_G(x)) \cap {\rm CM}_n^d$ is a variety, then if it has infinitely many points, it must contain a curve. In this case, we can find such a curve that also lies in the image of $\phi_n^d$ (this is me ignoring the issues that can arise when passing from a semi-algebraic set to its complex Zariski closure). Such a curve is a flex. ◊

The above proposition motivates the following general problem: for each $d \ge 1$, find a combinatorial description of $\mathcal{M}({\rm CM}_n^d)$, the algebraic matroid of the Cayley-Menger variety of $n$ points in $d$-dimensional space. For $d \ge 3$, this problem is open, and has been for at least a century. The $d = 1$ case is quite simple: $\mathcal{M}({\rm CM}_n^1)$ is the graphic matroid of the complete graph $K_n$, and you might be able to see this intuitively. There are a handful of characterizations for the $d=2$ case; perhaps the most famous, and elegant, due to Hilda Polaczek-Geiringer, is the following.

Theorem. A graph $G$ is independent in $\mathcal{M}({\rm CM}_n^d)$ if and only if every subgraph of $G$ on $k$ vertices has at most $2k-3$ edges.

The above theorem is known as Laman’s theorem, based on the mistaken, but previously widespread, belief that this result originated with Gerard Laman’s 1970 paper [3]. Recently however, it was noticed that Hilda Pollaczek-Geiringer had actually proven this result much earlier in 1927 [5].

Concluding remarks

Applied algebraic geometry is full of families of varieties whose algebraic matroids are worth understanding. As in the two examples above, the ground set of each such matroid is usually a graph, though sometimes the ground set is something slightly more complicated, like a gain graph as in [2]. There are many open problems, as well as opportunities to develop general theory that could be used to solve them.

References

[1] Daniel Irving Bernstein. Completion of tree metrics and rank 2 matrices. Linear Algebra and its Applications, 533:1–13, 2017. arxiv:1612.06797.

[2] Daniel Irving Bernstein. Generic symmetry-forced infinitesimal rigidity: translations and rotations. arXiv preprint arXiv:2003.10529, 2020.

[3] Gerard Laman. On graphs and rigidity of plane skeletal structures. Journal of Engi-neering mathematics, 4(4):331–340, 1970.

[4] Bernt Lindström. A non-linear algebraic matroid with infinite characteristic set. Discrete Mathematics, 59(3):319–320, 1986.

[5] Hilda Pollaczek-Geiringer. Über die gliederung ebener fachwerke. ZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik, 7(1):58–72, 1927.

Footnotes

  1. When applied algebraic geometers say “property $P$ is satisfied by a generic point of $V$,” it means that the set of points in $V$ where $P$ is not satisfied is contained in a subvariety of $V$. We use the word “generic” to avoid explicitly writing down what that variety is. When $V$ is irreducible, any subvariety of $V$ has lower dimension than $V$. Therefore, when $\mathbb{F} = \mathbb{C}$ or $\mathbb{R}$, if $V$ is irreducible and a generic point of $V$ satisfies property $P$, then a point randomly sampled from $V$ with respect to a reasonable probability distribution will satisfy $P$ with probability one.

The World of Clean Clutters, I: Ideal Clutters

Guest post by Ahmad Abdi

You may have heard of Paul Seymour’s f-Flowing Conjecture on binary matroids, perhaps as alluded to in these detailed posts (I, II, III) by Dillon Mayhew, or in connection with weakly bipartite graphs, or directly from the source. If you haven’t heard of it, or have but don’t remember much, or better yet, know it well but need a new lens to view the problem, it’s your lucky day! I’m here to tell you all about it.

For you to fully appreciate the conjecture though, I’ll have to put it in the proper context. That’ll require me to take you outside your comfort zone of matroids to the larger world of clutters, where I’ll be able to talk about ideal clutters and binary clutters. I’ll then be able to present the f-Flowing Conjecture, the latest progress made towards resolving it, as well as the tools that have made that possible.

But I won’t stop there. I’ll talk about an adjacent, intriguing class of clutters, those without an intersecting clutter as a minor, and then move my way up to the all-encompassing class of clean clutters (an oxymoron, I know!): a minor-closed class whose excluded minors come from degenerate projective planes and odd holes.

The world of clean clutters
labelclass nameconjecture
1Ideal CluttersEvery clutter in this class has bounded chromatic number.
2Binary CluttersThe f-Flowing Conjecture
3Clutters without an Intersecting MinorThe $\tau=2$ Conjecture
The classes of clutters surveyed in this series of posts

This series of posts is meant to provide a non-technical survey of the classes displayed below. I shall provide a historical account of each class, hopefully making it clear why the class is interesting, and then provide just one exciting conjecture to stimulate further research on the class.

This post focuses on the class of Ideal Clutters.

1.

Clutters form the framework for my post. I’m grateful that Dillon has already laid the basics in these posts: I, II, III, but let me recall a few definitions, as well as make some new ones; the careful reader will notice that my notation is slightly but harmlessly different from Dillon’s.

Let E be a finite set of elements, and let $\mathcal{C}$ be a family of subsets of E called members. $\mathcal{C}$ is a clutter over ground set E if no member contains another one.

A cover of $\mathcal{C}$ is a subset of E that intersects every member. Every superset of a cover is another cover, so not all covers are interesting from a clutter theoretic perspective, thereby leading us to the forthcoming adjective. A cover is minimal if it does not contain another cover.

By design, the family of minimal covers of $\mathcal{C}$ forms another clutter over the same ground set. This clutter is called the blocker of $\mathcal{C}$, and is denoted $b(\mathcal{C})$. Dillon has already proved the basic fact that the blocking relation is an involution, that is, $b(b(\mathcal{C}))=\mathcal{C}$.

Our choice of terminology for “clutter” and “blocker” follows the convention set forth by Jack Edmonds and Ray Fulkerson in this 1970 paper. The origin of the blocking relation, however, dates earlier to the theory of games, wherein the members of $\mathcal{C}$ represent the minimal winning coalitions, while the blocker takes an adversarial position, collecting all the minimal hitting sets, meant to tear down every winning coalition. For instance, these important 1958 and 1965 papers lay some of the foundational concepts in the study of clutters, predating the Edmonds-Fulkerson paper.

Given disjoint subsets $I,J\subseteq E$, $\mathcal{C}\setminus I/J$ denotes the clutter over ground set $E-(I\cup J)$ whose members are the inclusionwise minimal sets of $\{C-J: C\in \mathcal{C}, C\cap I=\emptyset\}$. This clutter is called the minor of $\mathcal{C}$ obtained after deleting $I$ and contracting $J$. This notion was coined in 1971 by Ray Fulkerson

You might find the notions of the blocker and clutter minors reminiscent of matroid duality and matroid minors, in which case you’d be happily surprised that the former two notions may in fact be viewed as extensions of the latter two. 

Photo by Bill Cook

For example, let $M$ be a matroid over ground set $E$, and take an element $f\in E$. Denote by $\mathrm{port}(M,f)$ the clutter over ground set $E-\{f\}$ whose members are $$\{C-\{f\} : C \text{ is a circuit of $M$ containing $f$}\}.$$ Seymour refers to this clutter as a port of $M$. He has shown that,

  • $b(\mathrm{port}(M,f)) = \mathrm{port}(M^\star,f)$ (Dillon proved this in his first post on clutters),
  • $\mathrm{port}(M,f)\setminus I/J = \mathrm{port}(M\setminus I/J,f)$ for disjoint $I,J\subseteq E-\{f\}$.

Thus, the two clutter notions are indeed extensions of matroid duality and matroid minors. One may have reached this conclusion alternatively by taking the clutter of bases, or circuits, of a matroid.

2.

Now that we’re done with the basics of Clutter Theory, we can move on to the main topic of this post: Ideal Clutters.

$\mathcal{C}$ is an ideal clutter if any of the following equivalent conditions are satisfied:

  1. Every vertex of the polyhedron $Q(\mathcal{C}):=\{x\in \mathbb{R}^E_+: x(C)\geq 1 ~ \forall C\in \mathcal{C}\}$ is integral. 
  2. For all cost vectors $c\in \mathbb{R}^E$, the linear program $$\text{minimize } c^\top x \text{ subject to } x\in Q(\mathcal{C})$$ if finite has an integral optimal solution.
  3. For all lengths $\ell\in \mathbb{R}^E_+$ and widths $w\in \mathbb{R}^E_+$, the width-length inequality holds: $$\min\{\ell(C):C\in \mathcal{C}\}\cdot \min\{w(B):B\in b(\mathcal{C})\}\leq \ell^\top w.$$

Here, $x(C)$ is short-hand notation for $\sum_{e\in C}x_e$.

The term ideal was coined in 1994 by Gérard Cornuéjols and Beth Novick, who used #1 as the main definition. This concept has been dubbed in the literature as the weak max-flow min-cut property, the max-flow min-cut property, the width-length property, or even the Fulkersonian property, all of which only speaks to the rich and tangled history of the concept, hinted at by the following table, displaying various classes of ideal clutters in the literature.

yearreferenceExamples of ideal clutters
1927
1956
1979
Menger
Ford and Fulkerson
Lehman
st-paths of a graph of a graph
1931König, Egreváryedges of a simple, bipartite graph
1938Gallai (a.k.a. Grünwald)directed st-paths of a digraph
1956Hoffman and Kruskaltotally unimodular matrices
1967Edmondsrooted arborescences of a digraph
1972Bergebalanced matrices
1973Edmonds and JohnsonT-joins of a graft
1979Lucchesi and Youngerdicuts of a digraph
1985
1994
Prodon
Goemans
Steiner cuts of a series-parallel digraph
2001Gueninodd circuits of a signed graph without an odd-K5 minor
2020Abdi, Cornuéjols, Guričanová and Leecube-ideal sets
A historical account of some classes of ideal clutters

In 1963 Alfred Lehman, inspired by Moore and Shannon’s landmark work on unreliable communication networks, studied the width-length inequality, condition #3, and proved it equivalent to #1, and also to what he called the max-flow min-cut equality, #2. In case you’re wondering what the terminology refers to, apply Strong Duality to the LP in #2.

The characterization #3 of idealness is particularly interesting due to its consequence that

the blocker of an ideal clutter is also ideal.

The blocking relation between clutters was later extended to polyhedra by Fulkerson, as documented in this RAND report. In the 1968 memorandum, he develops a geometric view of the blocking relation and gives another proof that idealness is closed under the blocking relation. Sadly, some authors fail to cite Lehman for this fact and only cite Fulkerson’s 1971 published version of the report, even though Ray himself cites Lehman for the fact. Understandably, Lehman did not put his 1963 memorandum in print until 1979!

3.

Not only is idealness closed under the blocking relation, but 

every minor of an ideal clutter is also ideal.

I leave the proof of this as an exercise for the reader; the only thing I’ll say is that there are three proofs, one corresponding to each characterization of idealness.

Given the fact above, a natural question arises:

What are the excluded minors for the class of ideal clutters?

A clutter is minimally non-ideal (mni) if it is non-ideal but every proper minor is ideal. Observe that a clutter is ideal if, and only if, it has no mni minor. In particular, the excluded minors for the class of ideal clutters are precisely the mni clutters.

Note that as idealness is closed under the blocking relation, and deletion/contraction corresponds to contraction/deletion in the blocker, the blocker of every mni clutter is another mni clutter.

In 1963, Lehman found four classes of mni minors, three of which formed infinite classes:

nameelementsmembersnotes
$\mathbb{L}_7$1,2,3,4,5,6,7{1,2,3}, {1,4,5},{1,6,7}, {2,4,7}, {2,5,6}, {3,4,6}, {3,5,7}The elements/members correspond to the points/lines of the Fano plane.

$b(\mathbb{L}_7) =\mathbb{L}_7$
$\Delta_n$, n=3,4,5,…1,2,3,…,n{1,2},{1,3},…,{1,n} and {2,3,…,n}The elements/members correspond to the points/lines of a degenerate projective plane.

$b(\Delta_n) =\Delta_n$
Odd hole of dimension n, n=5,7,9,…1,2,3,…,n{1,2},{2,3},{3,4}, …,{n-1,n},{n,1}In the literature, $\Delta_3$ is sometimes called an odd hole, too.
The blocker of an odd hole 1,2,3,…,nToo many to list.Every member has cardinality at least $\frac{n+1}{2}$.
The minimally non-ideal clutters found by Lehman in 1963

Lehman seems to have been discouraged by the multiplicity of the excluded minors:

“Whether or not this list is complete, the multiplicity of minimal matrices seems to preclude their usefulness as a W-L matrix characterization. (Cf. author’s foreword.)” 

These projective planes give rise to mni clutters.

In the foreword, which was added 17 years later in 1979 when the paper was finally published, he writes:

“More is known about minimal non-W-L matrices. U. Peled has found several additional classes of matrices which are also classically known in other contexts.”

I’m not sure what additional classes Uri Peled had found at the time but to this day, there are over 1500 small examples of mni clutters: See the paper by Cornuejols and Novick, as well as this paper by Lütolf and Margot. A new infinite class of mni clutters was also found 9 years ago (and don’t forget, the blocking clutters form another infinite class).

Odd holes, and their blockers, also give rise to mni clutters.

Lehman continues in the foreword:

“A consequence of a recent matrix theorem is apparently that the degenerate projective planes [i.e. the deltas] are the only minimal matrices requiring unequal weights.”

More specifically, the consequence of the “matrix theorem” states that for a minimally non-ideal clutter $\mathcal{C}$ different from $\Delta_4$, $\Delta_5$,…,, the width-length inequality is violated for $w=\ell={\bf 1}.$ Whereas for the mni clutters $\Delta_4$, $\Delta_5$,…, the width-length inequality is satisfied for $w=\ell={\bf 1}$.

The foreword above is the humblest of hints to one of the deepest results on ideal clutters, a result that dusted in Lehman’s desk drawer for over 10 years, until it finally appeared in 1990 at the request of Bill Cook and Paul Seymour in the first issue of DIMACS Series. A year later, Lehman won a Fulkerson prize for this “matrix theorem”. If you’re curious about the statement of this theorem, I urge you to read Chapter 9 of my notes, and in particular, Theorem 9.12.

A snapshot of Lehman’s handwritten manuscript on the special role of the deltas among minimally non-ideal clutters.

If you, like Lehman himself, are skeptical about the usefulness of his matrix theorem, the next post is bound to change your mind.

4.

Before I conclude with ideal clutters, let me leave you with a conjecture on idealness that Gérard Cornuéjols, Tony Huynh, Dabeen Lee, and I made in a paper whose extended abstract appeared in the proceedings of IPCO 2020, held online this past summer at the London School of Economics.

Suppose $\mathcal{C}$ has no member of cardinality one. A proper colouring of $\mathcal{C}$ is an assignment of colours to the elements so that there is no monochromatic member, that is, it consists of an assignment of an integer $\phi(e)$ to every element $e$ such that $\{\phi(e):e\in C\}$ has cardinality at least two. The chromatic number of $\mathcal{C}$ is the minimum number of colours used in a proper colouring.

Conjecture. There exists an integer $k\geq 4$ such that every ideal clutter without a member of cardinality one has chromatic number at most $k$.

Why $k$ should be at least four, and part of the origins of the conjecture, are explained in the paper. I hope the abrupt appearance of the conjecture is made up for by its utter simplicity.

Thank you for sticking around long enough to read this sentence. If you have any questions, feel free to ask them in the comment section below.

Ahmad Abdi, London School of Economics