Events - Department of Mathematics

View Full Calendar

Combinatorics Colloquium

Event Type
Department of Mathematics
245 Altgeld Hall
Sep 1, 2022   4:00 pm  
Igor Pak

Speaker: Igor Pak, UCLA
Title: Combinatorial inequalities
Abstract: 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. 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 these and other combinatorial inequalities. We then mention what does it mean not to have a combinatorial interpretation. Finally, I will briefly discuss our new framework of combinatorial atlas which allows one to give elementary proofs of the two results above, and extend them in several directions. The talk is aimed at the general audience.

link for robots only