For this post, I will give a brief introduction to the field of extended formulations.  This is a subject that is very much in vogue at the moment, with some outstanding recent breakthroughs that I will touch upon.  There are also a lot of nice matroidal results in this area, a few of which I will mention here, together with some conjectures.

The TSP polytope, TSP$(n) \in \mathbb{R}^{\binom{n}{2}}$ is the convex hull of the set of Hamiltonian cycles of the complete graph $K_n$.  The number of facets of TSP$(n)$ grows extremely quickly with $n$. For example, TSP$(10)$ has more than $50$ billion facets.  The central question of extended formulations is: what if we are looking at this problem in the wrong dimension?  That is, could there be a simple polytope in a higher dimensional space that projects down to the TSP polytope?  This motivates the notion of extension complexity.  Given a polytope $P$, the extension complexity of $P$, xc$(P)$ is

$$\min \{ \text{number of facets of $Q$: $Q$ projects to $P$}\}.$$

It may seem strange that increasing the dimension (adding more variables) can decrease the number of facets, but the following picture (thanks to Samuel Fiorini for permission to use it) shows that this is indeed possible.

In the 1980s, Swart [1] attempted to prove that there is a polytope with only polynomial many facets that projects down to the TSP polytope.  Note that a polynomial size extended formulation for the TSP polytope would imply P=NP.  The purported linear programs were extremely complicated to analyze.  However, in a breakthrough paper, Yannakakis [2] refuted all such attempts by showing that every symmetric linear program (LP) for the TSP polytope has exponential size.  Here symmetric means that each permutation of the cities can be extended to a permutation of the variables without changing the LP.  Since all the proposed LPs of Swart were symmetric, that was the end of the story (for then).

A lingering question however, was whether the symmetry condition was necessary. Yannakakis himself felt that asymmetry should not really help much.  However, in 2010, Kaibel, Pashkovich, and Theis [3] gave examples of polytopes that do not have polynomial size symmetric extended formulations, but that do have polynomial size asymmetric extended formulations.  This rekindled interest in the lingering question.  In another breakthrough paper in 2012, Fiorini, Masser, Pokutta, Tiwary, and de Wolf [4] finally proved that the TSP polytope does not admit any polynomial size extended formulation, symmetric or not.  Their proof uses the Factorization Theorem of Yannakakis. That is, the extension complexity of a polytope is actually just the non-negative rank of an associated matrix (called the slack matrix). To show that this non-negative rank is large for TSP$(n)$, they use a combinatorial lemma due to Razborov [5].

Of course, we can ask about the extension complexity of many other polytopes (including matroid polytopes) that arise in combinatorial optimization.  Another famous example is the perfect matching polytope, PM$(n)$, which is the convex hull of all perfect matchings of the complete graph $K_n$.  Note that we can optimize any linear objective function over the perfect matching polytope in strongly polynomial time via Edmond’s maximum matching algorithm.  Thus, it was quite surprising when Rothvoß [6] showed that PM$(n)$ does not admit any polynomial size extended formulation!

Given a matroid $M$, the independence polytope of $M$ is the convex hull of all independent sets of $M$.  Rothvoß [7] also proved that there exists a family of matroids such that their corresponding independence polytopes have extension complexity exponential in their dimension.  The fascinating thing about his proof, is that it is purely existential. That is, since it uses a counting argument for the number of matroids on $n$ elements due to Knuth [8], no explicit family of matroids is known.  Indeed, a nice recent observation of Mika Göös is that such an explicit family would imply the existence of explicit non-monotone circuit depth lower bounds (which no one knows how to do at the moment).

For positive results, Kaibel, Lee, Walter, and Weltge [9] showed that the independence polytopes of regular matroids have polynomial size extended formulations.  Their result uses Seymour’s Decomposition Theorem for regular matroids.

Another class of matroids with small extension complexity are sparsity matroids (which I will now define).  Let $G$ be a graph and let $k$ and $\ell$ be integers with $0 \leq \ell \leq 2k-1$. We say that $G$ is $(k, \ell)$-sparse if for all subsets of edges $F$, $|F| \leq \max \{k|V(F)|-\ell, 0\}$, where $V(F)$ is the set of vertices covered by $F$.  $G$ is $(k, \ell)$-tight if it is $(k, \ell)$–sparse and $|E(G)|=\max \{k|V(G)|-\ell, 0\}$.  Consider the subsets of edges $F$ of $G$ such that the graph $(V(G), F)$ is $(k, \ell)$–tight.  It turns out that such a collection of subsets is a matroid. Matroids arising in this way are called $(k, \ell)$-sparsity matroids.  Note that graphic matroids are $(1,1)$-sparsity matroids.  Iwata, Kamiyama, Katoh, Kijima, and Okamoto [10] recently proved that sparsity matroids have polynomial size extended formulations.

Both these examples are in some sense close to graphic matroids.  It may be that being ‘close’ to graphic is a sufficient condition for having compact extended formulations. Indeed, as far as I know the following conjectures are all open.

Conjecture 1.  The independence polytopes of signed graphic and even cycle matroids both have polynomial size extended formulations.

Conjecture 2.  The independence polytopes of a proper minor-closed class of binary matroids have polynomial size extended formulations.

Conjecture 3.  The independence polytopes of binary matroids have polynomial size extended formulations.

Conjecture 4.  For each finite field $\mathbb{F}$, the independence polytopes of $\mathbb{F}$-representable matroids have polynomial size extended formulations.

References.

[1] E. R. Swart. P = NP. Technical report, University of Guelph, 1986; revision 1987.

[2] M. Yannakakis. Expressing combinatorial optimization problems by linear programs (extended abstract). In Proc. STOC 1988, pages 223–228, 1988.

[3] V. Kaibel, K. Pashkovich, and D.O. Theis. Symmetry matters for the sizes of extended formulations. In Proc. IPCO 2010, pages 135–148, 2010.

[4] S. Fiorini, S. Massar, S. Pokutta, H. Tiwary, and R. de Wolf. Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In STOC, pages 95–106, 2012.

[5] A. A. Razborov. On the distributional complexity of disjointness. Theoret. Comput. Sci., 106(2):385– 390, 1992.

[6] T.Rothvoß. The matching polytope has exponential extension complexity, In STOC, New York, NY, USA, 2014, ACM, pp. 263–272.

[7] T.Rothvoß. Some 0/1 polytopes need exponential size extended formulations, Math. Program. Ser. A, (2012), pp. 1–14.

[8] D. E. Knuth. The asymptotic number of geometries, J. Combinatorial Theory Ser. A 16 (1974), 398–400.

[9] Kaibel, V., Lee, J., Walter, M., & Weltge, S. (2015). Extended Formulations for Independence Polytopes of Regular Matroids. arXiv preprint arXiv:1504.03872.

[10] Iwata, S., Kamiyama, N., Katoh, N., Kijima, S., & Okamoto, Y. (2015). Extended formulations for sparsity matroids. Mathematical Programming, 1-10.

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.

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

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