An edge-weighted graph , 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 to an antiferromagnetic graph 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 . In particular, we prove that, for any antiferromagnetic ,
holds, where denotes the complete bipartite graph minus a perfect matching . This confirms a conjecture of Sah, Sawhney, Stoner and Zhao for complete graphs . 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.