Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids!


Milena Mihail and Umesh Vazirani

I thank Nati Linial, Dan Spielman and Karim Adiprasito for sharing the news with me.

The Mihail-Vazirani conjecture for matroids and Feder-Mihail’s theorem

Consider a collection X of n vectors. A basis is a subset of X of linearly independent vectors that span the subspace spanned by X.  We can define a graph whose vertices are all bases and two bases are adjacent if their symmetric difference has two elements. Mihail and Vazirani conjectured that for every set Y of vertices in this graph the number of edges between Y to its complement \bar Y is at least \min (|Y| |,\bar Y|).

If X consists of the elements of the standard basis in \mathbb R^d and their negatives then the graph we obtain is the graph of the discrete n dimensional discrete cube and the assertion of the Mihail-Vazirani conjecture is well known.

The Mihail-Vazirani conjecture was formulated (and has now been proved) for arbitrary matroids. Think about a matroid as a collection K of subsets (the independent sets of the matroid) of some ground set X that closed under taking subsets (hence a simplicial complex) with the following property: For every Y \subset X, the induced simplicial complex on Y denoted by K(Y)  is pure. In other words, for every Y \subset X, all maximal independent subsets of Y have the same cardinality.

In a pioneering 1992 paper Tomás Feder and Milena Mihail proved the conjecture for balanced matroids.

Mihail and Vazirani conjecture for 0-1 polytopes.

An even more general conjecture by Mihail and Vazirani is still open. It asserts that for every 0-1 polytope, for every set Y of vertices, the number of edges between Y to its complement \bar Y is at least \min (|Y|, |\bar Y|).

The new breakthrough

Here is the link to the paper.

Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid by Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant

Let me mention another paper by a subset of the authors on related questions, another paper by Brändén and Huh, who independently proved the strong log-concavity of several of the polynomials appeared in the ALOV  paper, and are be several forthcoming papers by these two groups.

Here is the abstract: We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where 0<q<1. Consequently, we can sample random spanning forests in a graph and (approximately) compute the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has expansion at least 1. One of our key observations is a close connection between pure simplicial complexes and multiaffine homogeneous polynomials. Specifically, if X is a pure simplicial complex with positive weights on its maximal faces, we can associate with X a multiaffine homogeneous polynomial p_X such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of p_X.

Spectral negative dependence and Hodge-Riemann

A key paragraph regarding the method is the following:

“Our approach has a close connection to the original plan of Feder and Mihail (1992) who used the negative correlation property of balanced matroids to show that the bases exchange walk mixes rapidly. Unfortunately, most interesting matroids do not satisfy negative correlation. But it was observed [AKH18; HW16; AOV18] that all matroids satisfy a spectral negative dependence property.” AKH18 (a typo, it should be AHK18) is the solution for the Rota-Heron conjecture by Adiprasito, Huh and Katz that relies on the Hodge-Riemann property for matroids that we mentioned in this post. (I still feel in debt for a more detailed blog post about Adiprasito, Huh and Katz’ breakthrough!).”

I think that high dimensional expanders and random walks on them also plays a role in the new development.

Update: Related very recent papers

Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids

Authors: Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant

Log-Concave Polynomials III: Mason’s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids

Authors: Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant

Hodge-Riemann relations for Potts model partition functions

Authors: Petter Brändén, June Huh

Correlation bounds for fields and matroids

Authors: June Huh, Benjamin Schröter, Botong Wang

This entry was posted in Combinatorics, Computer Science and Optimization, Updates and tagged , , , , , , . Bookmark the permalink.

7 Responses to Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids!

  1. Eric Katz says:

    If I could rearrange the alphabet, I’d put K before H so it looks like I’m a higher-ranked author than June.

    GK: Dear Eric, this is a typo in the new paper. I made it clearer in the post.

  2. dsp says:

    May be a stupid question, but how do you prove the Mihail-Vazirani conjecture for the Boolean cube?

    • Gil Kalai says:

      This is a very wise question. There are various proofs and each proof can be seen as the beginning of a very nice story. One lovely proof is in terms of canonical paths which is a very fruitful idea. Another proof which gives precisely the same lower bound on the expansion in via the connection between expansion and eigenvalues. I will try to add useful links. Both proofs are described in this paper.

  3. Pingback: ICM 2018 Rio (4): Huh; Balog & Morris; Wormald | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s