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.

The Matroid Secretary Problem

In this post, I am going to discuss the matroid secretary problem, which is a very nice problem introduced by Babaioff, Immorlica, and Kleinberg [1].  I will try to give an up-to-date account, but am far from an expert in this area, so please feel free to comment if I miss or muddle anything.

Let’s warm up with the classical secretary problem, which has the following setup.  We want to hire a secretary.  There is a set $X$ of $n$ candidates, and each $x \in X$ has a competency $w(x)$.  We know that there are $n$ candidates, but we do not know the competency function.  The secretaries are then presented to us in a random order.  Once a secretary is presented to us, we interview him and discover his competence.  We then have to make an irrevocable decision to hire him or not.  If we hire him on the spot, the process ends.  If not, then due to a hyper-competitive labour market, he will be hired by another firm, and we must move on to the next candidate.

Let OPT be the maximum competency of all secretaries.  Our goal is to devise an algorithm that hires a secretary with competency close to OPT.  Say that an algorithm $\mathcal A$ is $\alpha$-competitive if OPT / $\mathbb{E} (\mathcal A) \leq \alpha$, where $\mathbb{E} (\mathcal A)$ is the expected competency outputted by $\mathcal A$ for a random permutation $\sigma$ of $X$.

Here is a $4$-competitive algorithm for the classical secretary problem.  We reject each of first $\frac{n}{2}$ candidates but we keep track of the highest competency, say $h$, of the first $\frac{n}{2}$ candidates.  We then hire the first candidate with competency at least $h$ (if none exists, we just hire the last secretary).  This algorithm is $4$-competitive because the probability that the most competent secretary is in the second half and the second most competent secretary is in the first half is more than $\frac{1}{4}$.  Interestingly, if we instead reject $\frac{1}{e}$ of the initial candidates, we obtain an $e$-competitive algorithm, which turns out to be best possible over all possible algorithms [2].

The matroid secretary problem has the same setup as above, except that there is a matroid $\mathcal M$ on the underlying set $X$ of secretaries.  We now want to hire a set of secretaries, subject to the condition that our hired set is independent in $\mathcal M$.  Again, there is an unknown weight function $w:X \to \mathbb R_+$, and the secretaries are presented to us in a random order.  After interviewing $x$, we must make an irrevocable decision to add or not add $x$ to our currently constructed independent set $I$.  Again, the goal is to devise an algorithm whose expected output is close to the maximum weight independent set.

Note that we recover the classical secretary problem when $\mathcal M$ is a rank-$1$ uniform matroid.  The generalization to matroids might seem like abstract nonsense, but the matroidal version is actually relevant in the theory of auctions, and has garnered a lot of interest.  The big (and still open) problem is the following conjecture.

Conjecture 1 (Babaioff, Immorlica, and Kleinberg [1]).  For every matroid $\mathcal M$, there is a $O(1)$-competitive algorithm.

Using a clever modification of the threshold price algorithm that we discussed for the classical secretary problem, Babaioff, Immorlica, and Kleinberg [1] proved that there is a $O(\log r)$-competitive algorithm, where $r$ is the rank of $\mathcal M$.  In a breakthrough paper, Chakraborty and Lachish [3] devised a $O(\sqrt{ \log r})$-competitive algorithm.  Their algorithm is a patchwork of a few different algorithms, and is quite complicated.  Finally, the state-of-the-art is a $O( \log \log r)$-competitive algorithm of Lachish [4].  Using different tools, Feldman, Svensson, and Zenklusen [5] have also obtained a $O( \log \log r)$-competitive algorithm for general matroids.

Another line of research is to weaken the problem slightly, in the hope of obtaining a constant-competitive algorithm.  Perhaps the most important modification is known as the random assignment model.  Note that in the original matroid secretary problem, we may as well assume that the weight function is chosen by an adversary.  In the random assignment model, we weaken the adversary, by only allowing her to choose the set of weights.  The weights are then randomly assigned to the set of secretaries.  Soto [6] proved that there is a constant-competitive algorithm for all matroids in the random assignment model.

Theorem 2 (Soto [6]). For each matroid $\mathcal M$, there is a $O(1)$-competitive algorithm in the random assignment model.

Soto’s algorithm uses the classic decomposition of a matroid into its principal minors.  See the recent paper of Fujishige [7] for a survey of this theory.  The principal minors of a matroid are uniformly dense ($\mathcal M$ is uniformly dense if $\max_{A \subseteq E} \frac{|A|}{r(A)}$ is obtained by $E$). Using the decomposition, one can reduce to the case of uniformly dense matroids, and Soto proved that there is indeed a $O(1)$-competitive algorithm for uniformly dense matroids. Note that his proof crucially assumes that we are in the random assignment model.

There are also many other interesting variants of the original matroid secretary problem. See Section 3 of Dinitz [8] for a nice overview.

I will finish by discussing the original matroid secretary problem for restricted classes of matroids.  In [1], it is proved that Conjecture 1 holds for graphic matroids, uniform matroids, partition matroids, and bounded-degree transversal matroids.  The bounded-degree condition for transversal matroids was later removed by Dmitrov and Plaxton [9].

Here is another class of matroids for which Conjecture 1 holds.  Let $\mathcal F$ be a laminar family and $c: \mathcal F \to \mathbb{N}$.  If we let $\mathcal I$ be the set of all $I$ such that $|I \cap F| \leq c(F)$ for all $F \in \mathcal F$, then $\mathcal I$ is the set of independent sets of a matroid.  Matroids arising in this way are called laminar matroids.  Note that the class of laminar matroids contains the partition matroids.  Im and Wang [10] showed that there is a constant-competitive matroid secretary algorithm for the class of laminar matroids.

Finally, Dinitz and Kortsarz gave a $O(1)$-competitive algorithm for the matroid secretary problem on regular matroids.  Their proof uses Seymour’s decomposition theorem for regular matroids [11].  Note that graphic matroids, cographic matroids, and $R_{10}$ all have $O(1)$-competitive matroid secretary algorithms.

Using the structure theorem for $\mathbb F$-representable matroids proved by Geelen, Gerards and Whittle [12], it may be possible to prove the following special case of Conjecture 1.

Conjecture 3.  For every finite field $\mathbb F$, there is a $O(1)$-competitive algorithm for the matroid secretary problem on the class of $\mathbb F$-representable matroids.

I suspect this might be tricky since one basic class of $\mathbb F$-representable matroids are those representable over a subfield $\mathbb F’$ of $\mathbb F$, and I don’t see how to get a $O(1)$-competitive matroid secretary algorithm for  $\mathbb F’$-representable matroids unless we are doing some cunning induction.

On the other hand, the structure theorem for binary matroids is slightly simpler (due to the absence of subfields), so the following special case of Conjecture 3 may be doable.

Conjecture 4. There is a $O(1)$-competitive algorithm for the matroid secretary problem on binary matroids.

References

[1] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. SODA, pages 434–443, 2007.

[2] E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl, 4, 1963.

[3] Sourav Chakraborty and Oded Lachish. Improved competitive ratio for the matroid secretary problem. In Proc. SODA, pages 1702–1712, 2012.

[4] Lachish, Oded. O(log log rank)-competitive ratio for the matroid secretary problem. Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on. IEEE, 2014.

[5] Feldman, Moran, Ola Svensson, and Rico Zenklusen.  A simple O(log log (rank))-competitive algorithm for the matroid secretary problem.  Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2015.

[6] José A. Soto. Matroid secretary problem in the random assignment model. In Proc. SODA, pages 1275–1284, 2011.

[7] S. Fujishige. Theory of principal partitions revisited. In Research Trends in Combinatorial Optimization, pages 127–162, 2009.

[8] Dinitz, Michael. Recent advances on the matroid secretary problem. ACM SIGACT News 44 (2013), no. 2, 126–142.

[9] Nedialko B. Dimitrov and C. Greg Plaxton. Competitive weighted matching in transversal matroids. In Proc. ICALP, pages 397–408, 2008.

[10] Sungjin Im and Yajun Wang. Secretary problems: laminar matroid and interval scheduling. In Proc. SODA, pages 1265–1274, 2011.

[11] P. D. Seymour. Decomposition of regular matroids. J. Combin. Theory Ser. B, 28(3):305–359, 1980.

[12] J. Geelen, B. Gerards, G. Whittle. Structure in minor-closed-classes of matroids. Surveys in Combinatorics, London Mathematical Society Lecture Note Series 409, 327–362, 2013.