Igor Pak, May 4, 2022


Combinatorial inequalities
May 4, 2022


New York
UTC -5

In the ocean of combinatorial inequalities, two islands are especially difficult. First, Mason's conjectures say that the number of forests in a graph with k edges is log-concave. More generally, the number of independent sets of size k in a matroid is log-concave. Versions of these results were established just recently, in a remarkable series of papers by Huh and others, inspired by algebro-geometric considerations.

Second, Stanley's inequality for the numbers of linear extensions of a poset with value k at a given poset element, is log-concave. This was originally conjectured by Chung, Fishburn and Graham, and famously proved by Stanley in 1981 using the Alexandrov–Fenchel inequalities in convex geometry. No direct combinatorial proof for either result is known. Why not?

In the first part of the talk we will survey a number of combinatorial inequalities. We then present a new framework of combinatorial atlas which allows one to give elementary proofs of the two results above, and extend them in several directions. This talk is aimed at the general audience.