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.

Continue reading

Lorentzian polynomials I: Theory

I’m organizing a reading seminar this semester on Lorentzian polynomials, mainly following this paper by Brändén and Huh but also covering some of the work of Anari et. al. In this post, I’d like to give a quick introduction to this active and beautiful subject. I’ll concentrate on the basic theory for now, and in a follow-up post I’ll discuss some of the striking applications of this theory.

One major goal of the theory of Lorentzian polynomials is to provide new techniques for proving that various naturally-occurring sequences of non-negative real numbers a_k are log-concave, meaning that a_k^2 \geq a_{k-1} a_{k+1} for all k. More generally, the authors consider homogeneous multivariate polynomials p(x_1,\ldots,x_n) with non-negative coefficients and study certain natural extensions of log-concavity to this setting. (For some background on log-concave sequences, see this survey paper which I wrote for the Bulletin of the AMS.) So let me begin by introducing two “classical” methods for proving (an even sharper version of) log-concavity of the coefficients of certain polynomials.

Continue reading

GAGS 2018

The 2018 Georgia Algebraic Geometry Symposium is a wrap!  This was the first time that the annual conference was held at Georgia Tech, and I thought it went very well.  Each of the eight talks seems to have been well-received, and some spectacular new results were announced.  Here’s a quick summary of (what I remember about) the talks: Continue reading

The Geometry of Break Divisors

I’d like to continue this discussion of break divisors on graphs & tropical curves by describing an interesting connection to algebraic geometry.  In this post, I’ll explain a beautiful connection to the theory of compactified Jacobians discovered by Tif Shen, a recent Ph.D. student of Sam Payne at Yale. Continue reading

Whitney Encounters of the Second Kind

I’m speaking tomorrow in the AMS Current Events Bulletin about the work of Adiprasito, Huh, and Katz on the Rota-Welsh conjecture and Hodge theory for matroids.   See this previous post for an introduction to their work.  [Note added 9/21/17: My write-up for the Current Events Bulletin can be found here.]

Here’s an excerpt from the last section of my slides which I may or may not have time to discuss in tomorrow’s talk.  It concerns this recent paper of June Huh and Botong Wang.  (Note added: As anticipated I did not have time to cover this material!  Here are the slides themselves: ceb_talk)

Continue reading

Matroids over Hyperfields, Part I

In this post and its sequel, I’d like to explain a new perspective on matroid theory which was introduced in this recent preprint which I wrote with Nathan Bowler.  The main observation is that by working with algebraic structures called hyperfields, in which addition is allowed to be multi-valued, linear subspaces, matroids, valuated matroids, and oriented matroids become special cases of a single general concept.  In the process of explaining this observation, I also hope to advertise how natural hyperfields are, for example in the context of tropical geometry.

Hyperstructures

The notion of an algebraic structure in which addition is allowed to be multi-valued goes back to Frédéric Marty, who introduced hypergroups in 1934.  Later on, in the mid-1950’s, Marc Krasner developed the theory of hyperrings and hyperfields in the context of approximating non-Archimedean fields, and in the 1990’s Murray Marshall explored connections to the theory of real spectra and spaces of orderings.  For the most part, however, the theory of hyperstructures was largely ignored by the mathematical community at large until Connes and Consani started advocating its potential utility in connection with F_1-geometry and the Riemann hypothesis.  There now seems to be a reappraisal of sorts going on within the math community of the “bias” against multi-valued operations.  Continue reading

Hodge Theory in Combinatorics

AHK_picture

From L to R: Karim Adiprasito, June Huh, Eric Katz

In January 2016, my colleague Josephine Yu and I are organizing a workshop called Hodge Theory in Combinatorics. The goal of the workshop is to present the recent proof of a 50-year-old conjecture of Rota by Karim Adiprasito, June Huh, and Eric Katz. In this post, I want to explain what the conjecture says and give a brief outline of its marvelous proof. I will follow rather closely this paper by Adiprasito-Huh-Katz (henceforth referred to as [AHK]) as well as these slides from a talk by June Huh. Continue reading