# 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

# The Drunkard’s Walk and Catalan Numbers

In this post, I’d like to present an amusing and off-the-beaten-path solution to the classical “Drunkard’s Walk” problem which at the same time derives the well-known generating function for the Catalan numbers.  This solution evolved from a suggestion by my former undergraduate student Stefan Froehlich during a discussion in my Math 4802 (Mathematical Problem Solving) class at Georgia Tech in Fall 2007.

In case you’re not familiar with it, here’s the problem (in a formulation I learned from this book by Frederick Mosteller):

A drunken man standing one step from the edge of a cliff takes a sequence of random steps either away from or toward the cliff. At any step, his probability of taking a step away from the cliff is $p$ (and therefore his probability of taking a step toward the cliff is $1-p$). What is the probability that the man will eventually fall off the cliff?

Continue reading

# The Circuit-Cocircuit Reversal System and Torsor Structures on Spanning Trees

The Jacobian of a finite graph $G$ is a finite abelian group whose cardinality is equal to the number of spanning trees of $G$.  In this earlier post, I discussed a family of combinatorial bijections between elements of ${\rm Jac}(G)$ and the set ${\mathcal T}(G)$ of spanning trees of $G$.  I also discussed the fact that for plane graphs, these Bernardi bijections come from a natural simply transitive action of ${\rm Jac}(G)$ on ${\mathcal T}(G)$ (or, more precisely, a natural isomorphism class of such actions).

In the present post, I’d like to discuss a different family of simply transitive actions of ${\rm Jac}(G)$ on ${\mathcal T}(G)$ discovered by myself, Spencer Backman (a former student of mine), and Chi Ho Yuen (a current student of mine).  One virtue of our construction is that it generalizes in a natural way from graphs to regular matroids.  (We will mostly stick to the graphical case in this post, but will insert some comments about extensions to regular and/or oriented matroids.  A regular matroid can be thought of, rather imprecisely, as the smallest natural class of objects which contain graphs and admit a duality theory generalizing duality for planar graphs. Regular matroids are special cases of the more general concept of oriented matroids.)

One of the main new ideas in [BBY] (as we will henceforth refer to our paper) is to use the torsor ${\rm Pic}^{g-1}(G)$ as an intermediate object rather than ${\rm Pic}^{g}(G)$.  The latter is canonically isomorphic (as a ${\rm Jac}(G)$-torsor) to the set of break divisors on $G$; the former is isomorphic to the circuit-cocircuit reversal system, which we now introduce.

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

# The Combinatorics of Break Divisors

I recently gave three lectures at Yale University for the Hahn Lectures in Mathematics.  The unifying theme of my talks was the notion of break divisor, a fascinating combinatorial concept related to the Riemann-Roch theorem for graphs.  Some applications of break divisors to algebraic geometry will be discussed in a follow-up post.

Break divisors on graphs

Let $G$ be a connected finite graph of genus $g = g(G)$, where $g := |E(G)| - |V(G)| + 1$.  Our central object of study will be the notion of a break divisor on $G$.  Recall that a divisor $D$ on a graph $G$ is an assignment of an integer $D(v)$ to each vertex $v$ of $G$.   The divisor $D$ is called effective if $D(v) \geq 0$ for all $v$; in this case, we often visualize $D$ by placing $D(v)$ “chips” at $v$.  And the degree of $D$ is the sum of $D(v)$ over all vertices $v$, i.e., the total number of chips.  By analogy with algebraic geometry, we write divisors on $G$ as formal sums $D = \sum_{v \in V(G)} D(v) (v)$, i.e., as elements of the free abelian group on $V(G)$.

A break divisor on $G$ is an effective divisor $D$ of degree $g$ such that for every connected subgraph $H$ of $G$, the degree of $D$ restricted to $H$ is at least $g(H)$.  In other words, there are $g(G)$ total chips and each connected subgraph $H$ contains at least genus-of-$H$ of these chips.  One surprising fact, proved in this paper (referred to henceforth as [ABKS]), is that the number of break divisors on $G$ is equal to the number of spanning trees of $G$. 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)

# p-adic Numbers and Dissections of Squares into Triangles

My thesis advisor Robert Coleman passed away two years ago today (see this remembrance on my blog).  One of the things I learned from Robert is that p-adic numbers have many unexpected applications (see, for example, this blog post).  Today I want to share one of my favorite surprising applications of p-adic numbers, to a simple problem in Euclidean geometry. Continue reading

# Matroids over Hyperfields, Part II

In Part I of this post, we defined hyperrings and hyperfields, gave some key examples, and introduced matroids over (doubly distributive) hyperfields in terms of Grassman-Plücker functions.  If $E=\{ 1,\ldots,m \}$ is a finite set and $K$ is a field, we saw that a $K$-matroid on $E$ is the same thing as a linear subspace of $K^m$, and if ${\mathbb K}$ is the Krasner hyperfield then a ${\mathbb K}$-matroid on $E$ is the same thing as a matroid in the usual sense.  Matroids over the hyperfield ${\mathbb S}$ of signs are the same thing as oriented matroids, and matroids over the tropical hyperfield ${\mathbb T}$ are the same thing as valuated matroids.  In this post we will give some “cryptomorphic” axiomatizations of matroids over hyperfields, discuss duality theory, and then discuss the category of hyperrings in a bit more detail. 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

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

# A Celebration of Independence

Yesterday marked the second anniversary of my blog, and today is the 239th birthday of the U.S. In celebration of Independence Day, I want to explain what matroids are. Matroids were invented by Hassler Whitney (and independently by Takeo Nakasawa) to abstract the notion of linear independence from vector spaces to a much more general setting that includes acyclicity in graphs. Other pioneering early work on matroids was done by Garrett Birkhoff and Saunders MacLane. Matroid theory is a rich subject about which we will only scratch the surface here. In particular, there are many different (“cryptomorphic“) ways to present the matroid axioms which all turn out to be (non-obviously) equivalent to one another. We will focus on just a couple of ways of looking at matroids, emphasizing their connections to tropical geometry. Continue reading

# The Mathematics of Marriage

It’s been a while since my last blog post — one reason being that I recently got married.  In honor of that occasion, and my return to math blogging, here is a post on Hall’s Marriage Theorem.

Consider the following game of solitaire: you deal a deck of cards into 13 piles of 4 cards each, and your goal is to select one card from each pile so that no value (Ace through King) is repeated.  It is a beautiful mathematical fact that this can always been done, no matter how the cards were originally dealt!

We will deduce this from a more general result due to Philip Hall commonly known as Hall’s Marriage Theorem.  Suppose you are given finite sets $A_1, A_2,\ldots, A_n$ and you wish to find distinct elements $x_1 \in A_1,\ldots, x_n \in A_n$.  (In our solitaire example, take $A_j$ to be the values of the cards in the $j^{\rm th}$ pile.)  Such a collection is called a transversal or SDR (system of distinct representatives).  Under what conditions is this possible?  Well, for a transversal to exist it is necessary that for each subset $J \subset \{ 1,\ldots, n \}$, the set $A_J:= \bigcup_{j \in J} A_j$ contains at least $\#J$ elements.  Hall’s theorem asserts that these conditions are also sufficient. Continue reading