Log-concavity of independence sets of claw-free graphs via stable polynomials

Algebraic and Enumerative Combinatorics

03 March 11:00 - 11:50

Jonathan Leake - University of California, Berkeley

In 2007, Chudnovsky and Seymour proved that the independence polynomial of a claw-free graph G is real-rooted. This implies log-concavity and unimodality of the number of independent sets of size k of a claw-free graph. They prove this result by inducting on certain subgraphs of G and showing "compatibility" of the associated independence polynomials. In this talk, we simplify their proof by generalizing to the multivariate independence polynomial of G. In fact we prove a more general result due to Engström, taking many aspects of polynomial stability theory (as in the work of Borcea and Brändén) as inspiration. As a comment, this work was done prior to the development of Lorentzian polynomials, and so connections to the Lorentzian notion are as-of-yet unknown. It would be interesting if such connections were to exist. (Note: this is joint work with Nick Ryder.)
Sara Billey
University of Washington
Petter Brändén
KTH Royal Institute of Technology
Sylvie Corteel
Université Paris Diderot, Paris 7
Svante Linusson
KTH Royal Institute of Technology


Svante Linusson


For practical matters at the Institute, send an e-mail to