PC Seminar: Rook matroids and log-concavity of P-Eulerian polynomials

Abstract: In 1972, while investigating the theory of monomer-dimer systems, Heilmann and Lieb proved that the matching polynomial of a graph is real-rooted. This seminal result spurred the application of the geometry of polynomials to algebraic combinatorics. In the spirit of the Heilmann-Lieb theorem, we consider the set of non-nesting rook placements on a skew Ferrers board and probe the distributional properties of its generating polynomial. Surprisingly, the answers are governed by a new matroidal structure that we dub the rook matroid. We will discuss some of the structural properties of the rook matroid in relation to other well-known classes of matroids. We also consider a poset-theoretic perspective of this problem and in doing so, make progress on a conjecture of Brenti (1989) on the log-concavity of P-Eulerian polynomials. In particular, this completes the story of the Neggers-Stanley conjecture in the case of naturally labeled posets of width two. This is joint work with Per Alexandersson.

This is a seminar in our seminar series on Probability and Combinatorics (PC).