Lorentzian Polynomials II: Applications

In this previous post, I described the basic theory of Lorentzian polynomials d’après Brändén and Huh. Now I’d like to describe some of the powerful applications of this theory, culling together results from papers by several different sets of authors. Our first application will be Mason’s Ultra-Log-Concavity Conjecture from 1972, established independently by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant in 2018.

Theorem: Let M be a matroid on n elements, and let I_k(M) denote the number of independent sets of size k in M. Then the sequence I_k(M) is ultra-log-concave.

A special case of this result (which seems to be no easier to prove than the general case) is the following: Let E be a set of n vectors in some finite-dimensional vector space, and let I_k denote the number of k-element linearly independent subsets of E. Then the sequence I_k is ULC.

Here is a brief outline of the proof, following a hybrid of [BH] and [ALOV3]. Let {\mathcal I} be the collection of independent sets of M, and let g_M(y,z_1,\ldots,z_n) be the homogenous generating function of {\mathcal I}, i.e., g_M(y,z_1,\ldots,z_n) = \sum_{I \in {\mathcal I}} y^{n-|I|} \prod_{i\in I} z_i. One shows that g_M is Lorentzian by first using a straightforward deletion-contraction argument to reduce to the rank 2 case and then applying Cauchy-Schwartz to verify the Lorentzian property of the resulting quadratic form. Now, it is a general fact (see Theorem 2.10 of [BH] or Lemma 2.2 of [ALOV3]) that specializations of Lorentzian polynomials, where we set certain variables equal to each other, are again Lorentzian. Setting all z_i equal to z, we see that the bivariate polynomial g_M(y,z) = \sum_{I \in {\mathcal I}} y^{n-|I|} \prod_{i\in I} z^{|I|} = \sum_{k=0}^n I_k(M) y^{n-k} z^k is Lorentzian, and in particular its coefficients I_k(M) form an ULC sequence.

As another application of Lorentzian polynomials, we now turn to the Mihail-Vazirani conjecture, which asserts that the expansion constant of the basis exchange graph of any matroid is at least 1. Here is a concrete special case of the conjecture (which again seems to be no easier to prove than the general case). Let E be a set of n vectors in some finite-dimensional vector space, and let W be the vector space spanned by E. A basis of E is a basis for W contained in E. Let G be the graph whose vertices correspond to bases of E, and whose edges correspond to bases B,B' whose symmetric difference has size 2. In this situation, the Mihail-Vazirani conjecture says that for every subset Y of vertices of G, the number of edges connecting Y to its complement \bar{Y} is at least {\rm min} (|Y|,|\bar{Y}|).

Theorem ([ALOV2]): The Mihail-Vazirani conjecture is true for every matroid M.

The proof of this result in [ALOV2] goes through the theory of Markov chains. Every matroid M of rank r on [n] = \{ 1,\ldots,n \} gives rise to a natural Markov chain M_\mu, where \mu is the uniform probability distribution on the bases of M. The Markov chain M_\mu corresponds to the random walk on the set of bases of M where, given a basis B, we first choose a random element e of B and then choose a basis B' uniformly at random from the set of all bases containing B \backslash \{ e \}. It is shown in [ALOV2] that the probability distribution \mu is Lorentzian, meaning that its homogeneous generating polynomial

g_\mu(y,x_1,\ldots,x_n) = \sum_{S \subset [n]} \mu(S) y^{n-|S|} \prod_{i\in S} x_i

is Lorentzian. This implies, according to [ALOV2], that the Markov chain M_\mu mixes rapidly, i.e., the Monte Carlo Markov chain method produces rapid convergence of any initial state to the stationary distribution \pi. This rapid mixing implies, via a well-known argument, the Mihail-Vazirani conjecture.

More precisely, it is shown in [ALOV2] that if P_\mu denotes the transition matrix of the Markov chain M_\mu and I_k is the number of k-element independent subsets of M, then P_\mu has at most |I_k| eigenvalues larger than 1 - \frac{k+1}{r} for each 1 \leq k \leq r-1. In particular, M_\mu has spectral gap at least 1/r. It follows from standard spectral theory arguments that for any 0 < \epsilon < 1 and any basis B of M, the mixing time t_B(\epsilon) := \min \{ t \in {\mathbb Z}_{\geq 0} \; : \; \| P_\mu^t(B,\cdot) - \pi \|_1 \} of M_\mu, where P_\mu^t(B,\cdot) denotes the distribution of the Markov chain at time t starting at B, is at most r^2 \log (n / \epsilon).

The rapid mixing of M_\mu for any matroid M has other interesting consequences in addition to the Mihail-Vazirani conjecture. For example, while counting the number of bases in a matroid is known to be #P-complete, the rapid mixing of M_\mu implies that there is a probabilistic algorithm to approximately count the number of bases in a matroid, up to a multiplicative error factor of 1 + \epsilon, in polynomial time. More precisely:

Theorem ([ALOV2]): There is a randomized algorithm which, for any rank r matroid M on [n] given by an independent set oracle, and any 0 < \delta, \epsilon < 1, counts the number of bases of M up to a multiplicative factor of 1\pm \epsilon with probability at least 1-\delta, with running time which is polynomial in n, r, 1/\epsilon, \log(1/\delta).

In [ALOV1], Anari et. al. give a different algorithm for approximately counting the number of bases of a matroid which is deterministic but has a slightly worse multiplicative error factor of 2^{-O(r)} rather than 1+\epsilon. This algorithm also relies on the theory of Lorentizan polynomials, but in a different way: they use the fact that \log g_M(y,z_1,\ldots,z_n) is concave as a function on the positive orthant to show that there is a convex program whose solution yields a good approximation to the number of bases of M. (Convex programming is a far-reaching generalization of linear programming which, like linear programming, provides efficient algorithms for solving certain types of optimization problems.) We refer to [ALOV1] for further details.

Here is one more application of Lorentzian polynomials, this time to the representation theory of the general linear group {\rm GL}_n({\mathbb C}). Let \lambda be a partition of n, identified with its corresponding Young diagram, and let {\mathcal T} = {\mathcal T}_\lambda be the collection of all semistandard Young tableaux with shape \lambda and entries in [n]. For T \in {\mathcal T}, let \mu_i(T) be the number of appearances of i among the entries of T. The vector \mu(T) = (\mu_1(T),\ldots,\mu_n(T)) is called the weight of T. The classical Schur polynomial corresponding to \lambda is generating function s_\lambda(x_1,\ldots,x_n) = \sum_{T \in {\mathcal T}} x^{\mu(T)} = \sum_{\mu} K_{\lambda \mu} x^\mu, where x^{\mu} = x_1^{\mu_1}\cdots x_n^{\mu_n}. The coefficients K_{\lambda \mu} are called Kostka numbers; they are special cases of what is known in representation theory as Littlewood-Richardson coefficients. The normalized Schur polynomial is the corresponding exponential generating function S_\lambda(x_1,\ldots,x_n) = \sum_{\mu} K_{\lambda \mu} \frac{x^\mu}{\mu !}.

Theorem ([HMMS]): For every partition \lambda, the normalized Schur polynomial S_\lambda(x_1,\ldots,x_n) is Lorentzian. In particular, for any weight \mu and any i,j \in [n] we have K_{\lambda \mu}^2 \geq K_{\lambda (\mu + e_i - e_j)} K_{\lambda (\mu - e_i + e_j)}.

This result verifies a special case of a conjecture of a conjecture of Okounkov about log-concavity of Littlewood-Richardson coefficients. In contrast to the applications of Lorentzian polynomials given in [BH], the theorem of [HMMS] makes use of non-trivial results from algebraic geometry. It would be interesting to have an “elementary” proof that normalized Schur polynomials are Lorentzian. The connection with representation theory is that the Schur module V(\lambda), which is an irreducible representation of {\rm GL}_n(\mathbb C) with highest weight \lambda, has a canonical weight decomposition V(\lambda) = \oplus_\mu V_{\lambda \mu} with {\rm dim} V_{\lambda \mu} = K_{\lambda \mu}. See [HMMS] for additional results and conjectures related to Kostka numbers and their generalizations.

Concluding remarks:

  1. The paper [BES] by Backman, Eur, and Simpson uses the theory of Lorentzian polynomials, together with a novel presentation for the Chow ring of a matroid, to give a new proof of Rota’s log-concavity conjecture. Their proof is simpler than the original proof by Adiprasito, Huh, and Katz in several key ways; for example, it avoids the technical notions of order filters and flips, and in the process replaces the intricate double induction in [AHK] with a single induction.
  2. Additional applications of Lorenztian polynomials are given in [BH] and in the paper [EH] by Eur and Huh.
  3. For more information about Lorentzian polynomials, I highly recommend this series of three videos by June Huh delivered as part of the MIT Simons Lectures.
  4. One can find a number of conjectures about log-concave sequences in this survey article by Richard Stanley. Some of these have now been settled using the theory of Lorentzian polynomials; it is natural to wonder which others might also now be within reach.

One thought on “Lorentzian Polynomials II: Applications

  1. Pingback: Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids! | Combinatorics and more

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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