Professor Eric Katz of the University of Waterloo and his colleagues Karim Adiprasito (Max Planck Society and Hebrew University) and June Huh (Clay Mathematical Institute and Princeton University) have proved Rota's 45-year old conjecture on the log concavity of the characteristic polynomial of matroids.
Mathematician Gian-Carlo Rota made his famous conjecture in his 1970 address to the International Congress of Mathematicians. The conjecture concerns matroids, the common combinatorial generalization of graphs and linear subspaces. There is a particular polynomial that one can associate with a matroid, called the characteristic polynomial. It is a generalization of the chromatic polynomial of a graph which counts the graph's proper colourings. It was observed that in every example, the coefficients of the characteristic polynomial had a property called log-concavity, which meant that the logarithms of the coefficients form a concave sequence. Rota conjectured that all matroids have this property. Yet, until this recent work, no one knew if every matroid has this property or a reason behind it.
The Adiprasito-Huh-Katz proof of Rota's log-concavity conjecture draws on earlier work of Huh, individually and jointly with Katz. The earlier results used powerful and deep methods from algebraic geometry which concerns algebraic varieties, the solution sets to systems of polynomial equations. The new results establish an algebraic geometric framework for matroids even though no algebraic variety is present.
June Huh and Eric Katz presented the proof of Rota's conjecture at the August 10-15 workshop on Positivity in Combinatorial Algebraic Geometry at the University of Oregon.
"It's pretty exciting to make such a big discovery in matroid theory. And it's fun that it relies on some techniques originating in a completely different branch of mathematics," Katz said. He continued, "The result is taking us some time to write up as we've all been traveling this summer. But we expect to circulate a preprint pretty soon. Maybe in six weeks. Two months, tops."