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:

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.
Additional applications of Lorenztian polynomials are given in [BH] and in the paper [EH] by Eur and Huh.
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.
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.

2 thoughts on “Lorentzian Polynomials II: Applications”

Pingback: Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids! | Combinatorics and more
Pingback: A Fields Medal for June Huh! | Matt Baker's Math Blog

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Lorentzian Polynomials II: Applications

2 thoughts on “Lorentzian Polynomials II: Applications”

Leave a Reply Cancel reply

Share this:

Like this:

Related

2 thoughts on “Lorentzian Polynomials II: Applications”

Leave a Reply Cancel reply