Séminaire Lotharingien de Combinatoire, 93B.14 (2025), 12 pp.

Joonkyung Lee, Jaeseong Oh and Jaehyeon Seo

Counting Homomorphisms in Antiferromagnetic Graphs via Lorentzian Polynomials

Abstract. 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 various graphs H satisfy the inequality

|Hom(H,G)|² ≤ |Hom(H × K₂,G)| for any antiferromagnetic G, where H × K₂ denotes the tensor product of H and K₂. As a corollary, this confirms conjectures of Zhao and of Sah, Sawhney, Stoner and Zhao for complete graphs K_d and adds many more instances. Our method uses the emerging theory of Lorentzian polynomials due to Brändén and Huh, which may be of independent interest.

Received: November 15, 2024. Accepted: February 15, 2025. Final version: April 1, 2025.

The following versions are available:

PDF (793 K)
TeX version