Joonkyung Lee (이준경), Counting homomorphisms in antiferromagnetic graphs via Lorentzian polynomials

An edge-weighted graph $G$, possibly with loops, is said to be antiferromagnetic if it has nonnegative weights and at most one positive eigenvalue, counting multiplicities. The number of graph homomorphisms from a graph $H$ to an antiferromagnetic graph $G$ generalises various important parameters in graph theory, including the number of independent sets and proper vertex colourings.

We obtain a number of new homomorphism inequalities for antiferromagnetic target graphs $G$. In particular, we prove that, for any antiferromagnetic $G$,

$|\mathrm{Hom}(K_d, G)|^{1/d} ≤ |\mathrm{Hom}(K_{d,d} \setminus M, G)|^{1/(2d)}$

holds, where $K_{d,d} \setminus M$ denotes the complete bipartite graph $K_{d,d}$ minus a perfect matching $M$. This confirms a conjecture of Sah, Sawhney, Stoner and Zhao for complete graphs $K_d$. Our method uses the emerging theory of Lorentzian polynomials due to Brändén and Huh, which may be of independent interest.

Joint work with Jaeseong Oh and Jaehyeon Seo.