Let H be a d-regular graph, and let G be a graph possibly with loops. Regard G 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(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.

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

The conjecture asks whether, for every $d$ -regular graph $H$ and every graph $G$ with at most one positive eigenvalue, the normalized homomorphism count is maximized by $K_{d,d}$ . The antiferomagnetic extension was formulated by Sah, Sawhney, Stoner, and Zhao and remains unresolved in general.

Known results

Zhao, 2018: the complete-target case, including some looped targets, was known; the general extension was stated as a conjecture.
Sah, Sawhney, Stoner, and Zhao, 2018: the complete-bipartite extremal bound was proved for triangle-free source graphs, including proper colorings.
The 2025 paper confirms the relevant inequality for semiproper colorings, namely complete targets possibly with loops.

2025 partial progress

The paper Counting homomorphisms in antiferromagnetic graphs via ... proves $\hom(H,G)^2\leq\hom(H\times K_2,G)$ when $H$ is formed by blowing up vertices of a bipartite graph into cliques, with further cases for $G=K_q$ . These results are presented as progress toward the conjecture, not a complete proof. A 2026 clique-minimization theorem concerns a different inequality and does not settle this problem.

Current status (as of September 2026): The conjecture is open in general, with partial results for structured source graphs and complete or looped complete targets.

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

Primary source

Progress summary

Solutions 0