SiGMa 2017 Recap

The Workshop on Structure in Graphs and Matroids (SiGMa 2017) just wrapped up a few weeks ago in Waterloo.  This was a continuation of similar workshops organized by Bert Gerards in 20082010, and 2012 and by Stefan van Zwam and Rudi Pendavingh in 2014 and 2016.

I would like to thank Jim Geelen, Peter Nelson, Luke Postle, and Stefan van Zwam (the organizers of this year’s workshop) who did an excellent job in choosing the program and making sure everything ran smoothly.  They even helped fellow Matroid Union blogger Nathan Bowler overcome Canadian Visa issues in time to give his (very nice) plenary talk (thanks also go to Alan).

This year the workshop was held in commemoration of William T. Tutte, who would have turned 100 this year.  See here for a short biography of Professor Tutte.  Some matroid theorists may not be aware of Tutte’s extremely important contributions as a code breaker at Bletchley Park during the Second World War.  The C&O Department at Waterloo has also been hosting a Distinguished Lecture Series in honour of Tutte this summer.  Click on this link for the list of speakers and to watch the videos on YouTube. SiGMa 2017 also featured a rare conference dinner speech by Jim Geelen on Tutte’s work.

In case you were not able to attend, all the talks from SiGMa 2017 were recorded and are now viewable on the C&O Department’s YouTube Channel.  The overall quality of talks was very high.  I won’t bias you with all of my personal favourites, but for example, all the plenaries and Paul Seymour were excellent.

Polymath 12: Rota’s Basis Conjecture

Polymath 12 has just recently launched, and the topic is Rota’s Basis Conjecture!  See this guest post by Jan Draisma for information on Rota’s Basis Conjecture.

The polymath projects are a sort of mathematical experiment proposed by Tim Gowers to see if massively collaborative mathematics is possible.  The proposed proof proceeds via a sequence of public comments on a blog.  The general idea is to blurt out whatever idea comes into your head to allow for rapid public dissemination.

Polymath 12 is hosted by Timothy Chow and you can click here to follow the progress or to contribute.

The Lights Out Game

In this short post, I will discuss a cute graph theory problem called the Lights Out Game. The set-up is as follows.  We are given a graph $G=(V,E)$, where we consider each vertex as a light.  At the beginning of the game, some subset of the vertices are ON, and the rest of the vertices are OFF.  We are allowed to press any vertex $v$, which has the effect of switching the state of $v$ and all of the neighbours of $v$.  The goal is to determine if it is possible to press some sequence of vertices to turn off all the lights.

The version of this game where $G$ is the $5 \times 5$ grid was produced in the real world by Tiger Electronics, and has a bit of a cult following.  For example, there is a dedicated wikipedia page and this site (from which I borrowed the image below) even has the original user manuals.

The goal of this post is to prove the following theorem.

Theorem. Let $G=(V,E)$ be a graph for which all the lights are initially ON.  Then it is always possible to press a sequence of vertices to switch all the lights OFF.

(Note that if not all the lights are ON initially, it will not always be possible to switch all the lights OFF.  For example, consider just a single edge where only one light is ON initially.)

Proof. Evidently, there is no point in pressing a vertex more than once, and the sequence in which we press vertices does not matter.  Thus, we are searching for a subset $S$ of vertices such that $|S \cap N[v]|$ is odd for all $v \in V$, where $N[v]$ is the closed neighbourhood of $v$ (the neighbours of $v$ together with $v$ itself).  We can encode the existence of such a set $S$ by doing linear algebra over the binary field $\mathbb{F}_2$.

Let $A$ be the $V \times V$ adjacency matrix of $G$, and let $B=A+I$. Note that the column corresponding to a vertex $v$ is the characteristic vector of the closed neighbourhood of $v$. Thus, the required set $S$ exists if and only if the all ones vector $\mathbb{1}$ is in the column space of $B$.  Since $B$ is symmetric, this is true if and only if $\mathbb{1}$ is in the row space of $B$.  Let $B^+$ be the matrix obtained from $B$ by adjoining $\mathbb{1}$ as an additional row. Thus, we can turn all the lights OFF if and only if $B$ and $B^+$ have the same rank.

Since this is a matroid blog, let $M(B)$ and $M(B^+)$ be the column matroids of $B$ and $B^+$ (over $\mathbb{F}_2$). We will prove the stronger result that $M(B)$ and $M(B^+)$ are actually the same matroid. Every circuit of $M(B^+)$ is clearly a dependent set in $M(B)$.  On the other hand let $C \subseteq V$ be a circuit of $M(B)$.  Then $\sum_{v \in C} \chi(N[v])=\mathbb{0}$, where $\chi(N[v])$ is the characteristic vector of the closed neighbourhood of $v$. Therefore, in the subgraph of $G$ induced by the vertices in $C$, each vertex has odd degree.  By the Handshaking Lemma, it follows that $|C|$ is even, and so $C$ is also dependent in $M(B^+)$.

Reference

Anderson, M., & Feil, T. (1998). Turning lights out with linear algebra. Mathematics Magazine, 71(4), 300-303.

Extended Formulations and Matroid Polytopes

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.

twistedcube

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.