KAIST Discrete Math Seminar

All finite graphs satisfy the two properties mentioned in the title. I will explain what I mean by this, and speculate on generalizations and interconnections. This talk will be non-technical: Nothing will be assumed beyond basic linear algebra.

Tropical Laplacian is a symmetric square matrix associated to a balanced graph on a sphere, defined in a similar way to the Laplacian of an abstract graph. We will see by examples how tropical Laplacian appears in the study of polytopes, matroids, and graphs. The speaker will pose many linear-algebra-level questions to audiences.

Let V be a subvariety of the complex projective space. The amoeba of V is the set of all real vectors log|x| where x runs over all points of V in the complex torus. The asymptotic behavior of the amoeba is given by a polyhedral fan called the Bergman fan of V. We use the tropical geometry of the Bergman fan to prove the log-concavity conjecture of Rota and Welsh over any field. This work is joint with Eric Katz and is based on arXiv:1104.2519.

The chromatic polynomial of a graph counts the number of proper colorings of the graph. We give an affirmative answer to the conjecture of Read (1968) and Welsh (1976) that the absolute values of the coefficients of the chromatic polynomial form a log-concave sequence. We define a sequence of numerical invariants of projective hypersurfaces analogous to the Milnor number of local analytic hypersurfaces. Then we show log-concavity of the sequence by answering a question of Trung and Verma on mixed multiplicities of ideals. The conjecture on the chromatic polynomial follows as a special case.