Sah–Sawhney–Stoner–Zhao conjecture on antiferromagnetic homomorphism maxima

From papers

Let HH be a dd-regular graph, and let GG be a graph possibly with loops. Regard GG as its symmetric adjacency matrix, and suppose that it has at most one positive eigenvalue. Sah–Sawhney–Stoner–Zhao conjecture. Then

hom(H,G)1/v(H)hom(Kd,d,G)1/(2d).\hom(H,G)^{1/v(H)} \leq \hom(K_{d,d},G)^{1/(2d)}.

This would generalize the Kahn–Zhao theorem and the corresponding result for complete target graphs, asserting that complete bipartite graphs maximize normalized homomorphism counts from regular graphs under the stated spectral condition. The conjecture is presented as open in the paper.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Joonkyung Lee, Jaeseong Oh and Jaehyeon Seo, “Counting homomorphisms in antiferromagnetic graphs via Lorentzian polynomials”, arXiv:2506.13659 (2025).

Solutions 0

No solutions have been posted yet.