Clutters II

The last time I wrote on this subject, I made the case that clutters are of fairly natural interest to matroid theorists, since they are combinatorial objects with a duality involution, along with operations of deletion and contraction that are swapped by duality. They also arise fairly naturally in integer programming. In one formulation, integer programming is the problem of finding an integral vector $x$ that minimises the quantity $w^{T}x$ ($w$ is a fixed vector of weights) subject to the constraints $x\geq \mathbf{0}$ and $Mx\geq b$, where $M$ is a matrix of constraints. (Every entry of $\mathbf{0}$ is zero, and all comparisons of vectors are done entrywise – $x\geq \mathbf{0}$ means that every entry of $x$ is non-negative.)

Many optimisation problems in combinatorics can be expressed as integer programs. In particular, several problems are equivalent to integer programs where $b$ is equal to the vector of all ones, and $M$ contains only zeroes and ones. It’s an easy exercise to show that finding a minimum-size vertex cover in a graph is one of these problems. So is finding a minimum-size $s$-$t$ cut in a network.

In these cases, we may as well assume that the support of no row in $M$ properly contains the support of another row: if $r$ and $r’$ are rows of $M$, and $r$ is equal to $1$ in every position that $r’$ is equal to $1$, then we might as well remove the row $r$. This does not change the solution space of the program at all. In other words, we may as well assume that the rows of $M$ are the characteristic vectors of the edges in a clutter.

So clutters arise from combinatorial optimisation problems, via integer programming, and this leads to the following Venn diagram.

ClutterVenn

My aim today is modest: to define these classes of clutters. The illustration, along with essentially all the content found here, is in Combinatorial Optimisation: Packing and Covering, by Gérards Cornuéjols.

First of all, let $H=(S,\mathcal{A})$ be a clutter, so that $S$ is a finite set, and the members of $\mathcal{A}$ are subsets of $S$, none of which is properly contained in another. Let $M(H)$ be the incidence matrix of $H$. That is, the columns of $M(H)$ are labelled by the elements of $S$, and the rows are labelled by members of $\mathcal{A}$. An entry of $M(H)$ is one if and only if the corresponding element of $S$ is contained in the corresponding member of $\mathcal{A}$, otherwise it is zero.

Now assume that $w$ and $x$ are $|S|\times 1$ vectors with rows labelled by elements of $S$ (in the same order as the columns of $M(H)$), and the entries of $w$ non-negative. The vector $w$ can be seen as assigning a weight to each element of $S$. We will consider the following integer program.

(1) Minimise $w^{T}x$ subject to the constraints $x\geq \mathbf{0}$ and $M(H)x\geq \mathbf{1}$.

(Here $\mathbf{1}$ is the vector of all ones.)

If $x$ is an integer solution to this problem, then there is no harm in assuming that the entries of $x$ are all $0$ or $1$. (If any entry is greater than $1$, then replace it with $1$. Then $M(H)x\geq \mathbf{1}$ will still hold, and $w^{T}x$ will not have increased.) So an integer solution can be seen as a characteristic vector of a subset of $S$. This subset must intersect every member of $\mathcal{A}$ (by virtue of the constraint $M(H)x\geq \mathbf{1}$). Thus we are looking for a minimum-weight hitting set, and (1) can be thought of as the relaxation of the hitting set problem that allows non-integral solutions.

Next we consider the dual problem. Here $y$ is a $|\mathcal{A}|\times 1$ vector with entries labelled by the members of $\mathcal{A}$.

(2) Maximise $y^{T}\mathbf{1}$ subject to the constraints $y\geq \mathbf{0}$ and $y^{T}M(H)\leq w$.

In this problem we are thinking of $w$ as a capacity on each element of $S$. The vector $y$ assigns a non-negative flow value to each edge in $\mathcal{A}$, and the constraint $y^{T}M(H)\leq w$ says that the sum of flows over the edges that contain an element $s\in S$ cannot exceed the capacity that $w$ assigns to $s$. A solution to (2) maximises the sum of the flow values.

Now we can define the four classes in the Venn diagram.

$H$ has the Max Flow Min Cut property if, for every non-negative integer vector $w$, the programs (1) and (2) both have optimal solutions, $x$ and $y$, that are integral.

$H$ has the packing property if, for every vector $w$ whose entries are $0$, $1$, or $+\infty$, the programs (1) and (2) both have optimal solutions that are integral. In program (1), a weight of $+\infty$ means that we try to never include that element of $S$ in our hitting set. A weight of $0$ means that we can include that element for free.

$H$ packs if programs (1) and (2) have optimal solutions that are integral vectors when $w$ is set to be $\mathbf{1}$.

$H$ is ideal if, for any choice of vector $w$ with non-negative entries, not necessarily integral, program (1) has an optimal solution that is an integral vector.

Next time I will say more about the relations between these properties. For now, I will just note that, rather unfortunately, there really are clutters that pack, but which do not have the packing property. On the other hand, the shaded area of the Venn diagram is believed to be empty. So it is conjectured that a clutter has the Max Flow Min Cut property if and only if it has the packing property. Cornuéjols offers a bounty of $5000 for a resolution of this conjecture (or one of 17 others) before 2020.

Whittle’s Stabilizer Theorem

Representable matroids are an attractive subclass of matroids, because in their study you have access to an extra tool: a matrix representing this matroid. This is a concise way to describe a matroid: $O(n^2)$ numbers as opposed to $O(2^{2^n})$ bits declaring which subsets are (in)dependent. Let $M$ be a matroid, and $A$ a representation matrix of $M$. The following operations do not change the matroid:

  • Add a multiple of a row of $A$ to another row of $A$;
  • Scale a row of $A$ by a nonzero constant;
  • Scale a column of $A$ by a nonzero constant;
  • Add or remove all-zero rows;
  • Apply a field automorphism to each entry of $A$.

If a matrix $A_1$ can be turned into a matrix $A_2$ through such operations, then we say $A_1$ and $A_2$ are equivalent. If we don’t use any field automorphisms, then we say they are projectively equivalent. Generally, a matroid can have multiple inequivalent representations over a field. The exceptions are the finite fields $\textrm{GF}(2)$ and $\textrm{GF}(3)$ (shown in [BL]).

When we try to prove some theorem about a matroid or class of matroids, inequivalent representations can be a major complicating factor. For instance, the excluded-minor characterization of ternary matroids can be proven in under five pages [Oxley, pp. 380-385], whereas the excluded-minor characterization of quaternary matroids takes over fifty [GGK]. It is not surprising, then, that significant efforts have been made to get a handle on inequivalent representations. In this post I will focus on one such effort, namely a very attractive theorem by Geoff Whittle, who recently celebrated his 65th birthday with a wonderful workshop. First, a definition.

Definition. Let $\mathbb{F}$ be a field, and $\mathcal{M}$ a minor-closed class of $\mathbb{F}$-representable matroids. Let $N \in \mathcal{M}$. We say $N$ is a stabilizer for $\mathcal{M}$ if, for every 3-connected matroid $M \in \mathcal{M}$ that has $N$ as a minor, each representation of $N$ (over $\mathbb{F}$) extends to at most one representation of $M$ (up to the equivalence defined above).

In other words, once we select a representation for $N$, we have uniquely determined a representation of $M$. A small example: let $\mathbb{F} = \textrm{GF}(5)$, let $\mathcal{M}$ be the set of all minors of the non-Fano matroid $F_7^-$, and let $N$ be the rank-3 wheel. Now $N$ has the following representation:

$$
\begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 1 & 1 & 0\\
0 & 0 & 1 & 0 & 1 & a
\end{bmatrix}
$$

where $a \in \{1, 2, 3\}$. The only 3-connected matroids in $\mathcal{M}$ that have $N$ as a minor are $N$ itself and $F_7^-$. We need to check that each representation of $N$ extends to at most one representation of $F_7^-$. Up to equivalence, the latter representation must look like

$$
\begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 1 & 1\\
0 & 1 & 0 & 1 & 1 & 0 & b\\
0 & 0 & 1 & 0 & 1 & a & c
\end{bmatrix}
$$

and it is readily checked that we must have $b = c = a = 1$. Hence two of the representations of $N$ do not extend to a representation of $M$, whereas one extends uniquely to a representation of $M$. So $N$ is a stabilizer for $\mathcal{M}$.

If $\mathcal{M}$ is an infinite class, we cannot do an exhaustive check as in the example to verify a stabilizer. But Geoff Whittle managed to prove that a finite check still suffices:

Whittle’s Stabilizer Theorem [Whi]. Let $\mathcal{M}$ be a minor-closed class of $\mathbb{F}$-representable matroids, and $N \in \mathcal{M}$ a 3-connected matroid. Exactly one of the following holds:

  • $N$ is a stabilizer for $\mathcal{M}$ over $\mathbb{F}$;
  • There is a 3-connected matroid $M \in \mathcal{M}$ such that either:
    • $N = M\backslash e$ and some representation of $N$ extends to more than one representation of $M$;
    • $N = M / e$ and some representation of $N$ extends to more than one representation of $M$;
    • $N = M / e \backslash f$, $M / e$ and $M \backslash f$ are 3-connected, and some representation of $N$ extends to more than one representation of $M$.

I will conclude this post with two applications. I will leave the finite case checks to the reader.

Lemma. The matroid $U_{2,4}$ is a stabilizer for the class of quaternary matroids.

Corollary [Kah]. A 3-connected, quaternary, non-binary matroid has a unique representation over $\textrm{GF}(4)$.

Proof. A non-binary matroid $M$ has a $U_{2,4}$-minor. The matroid $U_{2,4}$ has the following representation:

$$
\begin{bmatrix}
1 & 0 & 1 & 1\\
0 & 1 & 1 & a
\end{bmatrix}
$$
where $a \not\in \{0,1\}$. This leaves two choices for $a$, that are related through a field automorphism. Hence $U_{2,4}$ has (up to equivalence) a unique representation over $\textrm{GF}(4)$. But $U_{2,4}$ is a stabilizer, so $M$ is uniquely representable over $\textrm{GF}(4)$ as well. $\square$

Lemma. The matroids $U_{2,5}$ and $U_{3,5}$ are stabilizers for the class of quinary matroids.

Lemma. The matroid $U_{2,4}$ is a stabilizer for the class of quinary matroids with no minor isomorphic to $U_{2,5}$ and $U_{3,5}$.

Corollary [OVW]. A 3-connected, quinary matroid has at most six inequivalent representations over $\textrm{GF}(5)$.

Proof. $U_{2,5}$ and $U_{3,5}$ have six inequivalent representations and are stabilizers. If $M$ does not have such a minor, then either $M$ is regular (and thus uniquely representable over any field) or $M$ has a $U_{2,4}$-minor, which is has three inequivalent representations. $\square$

References

  • [BL] Tom Brylawski and Dean Lucas, Uniquely representable combinatorial geometries. In Teorie Combinatorie (proc. 1973 internat. colloq.) pp. 83-104 (1976).
  • [GGK] Jim Geelen, Bert Gerards, Ajai Kapoor, The excluded minors for $\textrm{GF}(4)$-representable matroids. J. Combin. Th. Ser. B, Vol. 79, pp. 247-299 (2000).
  • [Kah] Jeff Kahn, On the uniqueness of matroid representations over $\textrm{GF}(4)$. Bull. London Math. Soc. Vol. 20, pp. 5–10 (1988).
  • [OVW] James Oxley, Dirk Vertigan, Geoff Whittle, On inequivalent representations of matroids over finite fields.J. Combin. Theory Ser. B. Vol. 67, pp. 325–343 (1996).
  • [Oxley] James Oxley, Matroid Theory, 2nd edition. Oxford University Press (2011).
  • [Whi] Geoff Whittle, Stabilizers of classes of representable matroids. J. Combin. Theory Ser. B, Vol. 77, pp. 39–72 (1999).

The limits of structure theory?

This post is about some conjectures on matroid minor structure theory in the most general setting possible: excluding a uniform matroid. Jim Geelen previously discussed questions in this area in [1], and most of what I write here comes from discussions with him.

Whether they be for graphs or matroids, qualitative structure theorems for minor-closed classes usually fit a particular template. They make a statement that the members of a minor-closed class are ‘close’ to having a particular basic structure, where the structure should be something that differs the graphs/matroids in the class from arbitrary/random ones. In the case of proper minor-closed classes of graphs, this structure takes the form of embeddability on a fixed topological surface, as was famously shown by Robertson and Seymour. For matroids representable over a fixed finite field, the structure arises from classes of group-labelled graphs that embed on a fixed topological surface, classes of group-labelled graphs in general, and (when the order of the field is non-prime) classes of matroids representable over a fixed subfield. These results for finite fields have been shown in recent years by Geelen, Gerards and Whittle, and have already given us powerful tools for understanding the matroids in minor-closed classes, as demonstrated most notably in their proof of Rota’s conjecture.

Extending graph minors structure theory to minor-closed classes of matroids over finite fields was no mean feat, but there is real reason to believe that we can generalise it further.  It seems unlikely that one could obtain very strong structural results for all minor-closed classes; for example, the class of sparse paving matroids (that is, the matroids whose girth is at least the rank and whose cogirth at least the corank) is minor-closed, and is conjectured to contain almost all matroids – intuitively, a structure theorem that allows us to ‘understand’ the class of sparse paving matroids seems unlikely. The sticking point here seems to be that this class contains all uniform matroids. At the moment, we think that one should be able to obtain sensible qualititative structure theorems precisely for the minor-closed classes that don’t contain all the uniform matroids. In this post, I’ll state a conjectures that makes this kind of statement. For this, we need two ingredients.

Basic Structures

We first need an idea which basic structures we expect to see as outcomes. These turn out to be pretty close to what goes on in the finite field representable case. Let $\mathcal{M}$ be a minor-closed class not containing all uniform matroids. Let $U$ be a uniform matroid not contained in $\mathcal{M}$. Without loss of generality, we may assume that $U = U_{s,2s}$ where $s \ge 4$, as every uniform matroid is a minor of a matroid of this form. Here are some examples of interesting classes that  $\mathcal{M}$ could be:

  • The class of $\mathbb{F}$-representable matroids, where $\mathbb{F}$ is some finite field over which $U$ is not representable.
  • The class of graphic matroids.
  • The class of bicircular matroids. (These are the ‘graph-like’ matroids in which each edge element is placed freely on the line between two vertex elements).
  • The class of frame matroids (i.e. the matroids of the form $M \backslash V$, where $V$ is a basis of a matroid $M$ for which every fundamental circuit has size at most two). This class contains both the previous ones, as well as various other graph-like matroids such as those arising from group-labelled graphs. $U_{4,8}$ is not a frame matroid and therefore neither is $U$.
  • The class of duals of frame matroids. (Or graphic/bicircular matroids)
  • A class of matroids arising (as graphic, cographic, bicircular, group-labelled-graphic, etc…)  from the class of graphs that embed on some surface.

Although they are not at all trivial from a graph-theoretic perspective, classes of the last type are less rich as they all have small vertical separations. Classes of the the other types, however, contain matroids of arbitrarily high vertical connectivity. Structural statements simplify a lot when they are made about highly connected matroids, and the main conjecture I’ll be stating will apply only to very highly vertically connected matroids in a given minor-closed class; the last type of class will therefore not show up.

The divide between the ‘highly connected’ minor-closed classes and other classes is made concrete by the following conjecture.

Conjecture 1. Let $\mathcal{M}$ be a minor-closed class of matroids not containing all uniform matroids. Either

  • $\mathcal{M}$ contains the graphic matroids or their duals,
  • $\mathcal{M}$ contains the bicircular matroids or their duals, or
  • there is an integer $t$ so that $\mathcal{M}$ does not contain any vertically $t$-connected matroid on at least $2t$ elements.

Closeness 

We now need to say what, according to our structural conjecture, exactly is meant by two matroids being ‘close’. For minor-closed classes of graphs, ‘closeness’ is measured in terms of vortices, apex vertices, and clique-sums. For matroids over finite fields, the structure theory considers two matroids on the same ground set to be ‘close’ if they have representations that differ by a bounded-rank matrix. None of these ideas quite work for matroids in general, as we don’t have representations, let alone vertices. However, there is something that will.

single-element projection of a matroid $M$ is a matroid $N$ for which there exists a matroid $L$ such that $L \backslash e = M$ and $L / e = N$. If $N$ is a single-element projection of $M$ then $N$ is a single-element lift of $M$. Single-element lifts and projections are dual notions that ‘perturb’ a matroid by a small amount to another matroid on the same ground set; for example, they change the rank and corank of any given set by at most $1$. We write $\mathrm{dist}(M,N)$ to denote the minimum number of single-element lifts and/or projections to transform $M$ into $N$. If this ‘distance’ is small, then $M$ and $N$ are ‘close’. This will serve as the notion of closeness in our structure conjecture. (In a more general structure theory, vortices will also arise). This distance only makes sense if $M$ and $N$ have the same ground set, if this is not the case, then we say $\mathrm{dist}(M,N) = \infty$.

Incidentally (and I’m looking at you, grad students), I would like an answer to the following question, which would simplify the notion of perturbation distance – I don’t have a good intuition for whether it should be true or false, and either way it could be easy.

Problem. Let $M$ and $N$ be matroids for which there exists a matroid $L$ that is a single-element lift of both $M$ and $N$. Does there exist a matroid $P$ that is a single-element projection of both $M$ and $N$?

The Conjecture

Here goes! If $\mathcal{M}$ is a minor-closed class not containing all uniform matroids, then the highly connected members of $\mathcal{M}$ should be close to being frame, co-frame, or representable.

Conjecture 2: Let $\mathcal{M}$ be a minor-closed class of matroids not containing a uniform matroid $U$. There is an integer $t \ge 0$ so that, if $M$ is a vertically $t$-connected matroid in $\mathcal{M}$, then there is a matroid $N$ such that $\mathrm{dist}(M,N) \le t$ and either

  • $N$ is a frame matroid,
  • $N^*$ is a frame matroid, or
  • $N$ is representable over a field $\mathbb{F}$ for which $U$ is not $\mathbb{F}$-representable.

If true, this conjecture would tell us that minor-closed classes of matroids inhabit a very beautiful universe. The hypotheses are very minimal, applying to a massive variety of different $\mathcal{M}$. The conclusions, on the other hand, imply that all ‘nondegenerate’ members of $\mathcal{M}$ are at a small distance from a matroid $N$ that is very far from being generic. Somehow, as happens again and again in matroid theory, the ‘special’ classes of representable and graph-like matroids are in fact fundamental to understanding the minor order.

Conjecture 2 is one of the many goals of a more general matroid structure theory; in my next post I will discuss some recent progress we have made towards it.

Reference

[1] Some open problems on excluding a uniform matroid, J. Geelen, Adv. Appl. Math. 41 (2008), 628-637.

Google Summer of Code 2015: outcomes

Guest post by Chao Xu

In the summer, I have extended the SAGE code base for matroids for Google Summer of Code. This post shows a few example of it’s new capabilities.

Connectivity

Let $M$ be a matroid with groundset $E$ and rank function $r$. A partition of the groundset $\{E_1,E_2\}$ is a $m$-separation if $|E_1|,|E_2|\geq m$ and $r(E_1)+r(E_2)-r(E)\leq m-1$. $M$ is called $k$-connected if there is no $m$-separation for any $m < k$. The Fano matroid is an example of $3$-connected matroid.

The Fano matroid is not $4$-connected. Using the certificate=True field, we can also output a certificate that verify its not-$4$-connectness. The certificate is a $m$-separation where $m < 4$. Since we know Fano matroid is $3$-connected, we know the output should be a $3$-separation.

We also have a method for deciding $k$-connectivity, and returning a certificate.

There are 3 algorithms for $3$-connectivity. One can pass it as a string to the algorithm field of is_3connected.

  1. "bridges": The $3$-connectivity algorithm Bixby and Cunningham. [BC79]
  2. "intersection": the matroid intersection based algorithm
  3. "shifting": the shifting algorithm. [Raj87]

The default algorithm is the bridges based algorithm.

The following is an example to compare the running time of each approach.

The new bridges based algorithm is much faster than the previous algorithm in SAGE.

For $4$-connectivity, we tried to use the shifting approach, which has an running time of $O(n^{4.5}\sqrt{\log n})$, where $n$ is the size of the groundset. The intuitive idea is fixing some elements and tries to grow a separator. In theory, the shifting algorithm should be fast if the graph is not $4$-connected, as we can be lucky and find a separator quickly. In practice, it is still slower than the optimized matroid intersection based algorithm, which have a worst case $O(n^5)$ running time. There might be two reasons: the matroid intersection actually avoids the worst case running time in practice, and the shifting algorithm is not well optimized.

Matroid intersection and union

There is a new implementation of matroid intersection algorithm based on Cunningham’s paper [Cun86]. For people who are familiar with blocking flow algorithms for maximum flows, this is the matroid version. The running time is $O(\sqrt{p}rn)$, where $p$ is the size of the maximum common independent set, $r$ is the rank, and $n$ is the size of the groundset. Here is an example of taking matroid intersection between two randomly generated linear matroids.

Using matroid intersection, we have preliminary support for matroid union and matroid sum. Both construction takes a list of matroids.

The matroid sum operation takes disjoint union of the groundsets. Hence the new ground set will have the first coordinate indicating which matroid it comes from, and second coordinate indicate the element in the matroid.

Here is an example of matroid union of two copies of uniform matroid $U(1,5)$ and $U(2,5)$. The output is isomorphic to $U(4,5)$.

One of the application of matroid union is matroid partitioning, which partitions the groundset of the matroid to minimum number of independent sets. Here is an example that partitions the edges of a graph to minimum number of forests.

Acknowledgements

I would like to thank my mentors Stefan van Zwam and Michael Welsh for helping me with the project. I also like to thank Rudi Pendavingh, who have made various valuable suggestions and implemented many optimizations himself.

References

[BC79] R.E Bixby, W.H Cunningham. Matroids, graphs and 3-connectivity, J.A Bondy, U.S.R Murty (Eds.), Graph Theory and Related Topics, Academic Press, New York (1979), pp. 91-103.

[Raj87] Rajan, A. (1987). Algorithmic applications of connectivity and related topics in matroid theory. Northwestern university.

[Cun86] William H Cunningham. 1986. Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15, 4 (November 1986), 948-957.