An entropy bridge from weighted to spectral Turán theorems

Abstract

We establish an entropy bridge, and then use it to prove that for any color-critical graph $F$ with chromatic number $\chi (F)=r+1\ge 3$, there exists a constant ${\lambda }_0={\lambda }_0(F)$ such that if $G$ is an $F$-free graph with $\lambda (G)\ge {\lambda }_0$, then for every $\ell \ge 1$ with $(r,\ell )\ne (2,2)$, \[ λ^\ell (G) \le \Big(1-\frac1r\Big)w_\ell(G), \] with equality if and only if $G$ is a regular complete $r$-partite graph; in the case $r=2$ with $\ell$ even, equality holds for every complete bipartite graph. The pair $(r,\ell )=(2,2)$ must be excluded, since the bound fails for several forbidden graphs, e.g., $C_{2t+1}$ with $t\ge 2$. Moreover, walks counts may also be replaced by the homomorphism counts of unbalanced trees. As further applications, we extend a spectral supersaturation result of Bollobás and Nikiforov [J. Combin. Theory Ser. B (2007)], and we also extend the entropic Turán theorem of Chao and Yu [J. London Math. Soc. (2026)] from $K_{r+1}$-free graphs to $F$-free graphs with $F$ color-critical. We provide a framework by passing through weighted Turá theorems of independent interest. If $G$ is $F$-free and $\mathbf{p}$ is a probability vector on $V(G)$ with $\Vert \mathbf{p}{\Vert }_{\infty }$ sufficiently small, then \[ 2\sum_{uv\in E(G)}p_up_v \le 1-\frac1r + o(1), \] and the error term $o(1)$ can be removed if and only if $F$ is color-critical. This is a Motzkin-Straus-type inequality in which the clique number of $G$ is replaced by $\chi (F)-1$. The proof of this weighted result combines a blow-up argument, the graph removal lemma, the Erdős-Simonovits stability theorem, a probabilistic sampling argument, and an exact estimate near a complete $r$-partite graph. The bridge linking spectral inequalities to weighted inequalities is based on the entropy method for the Markov chain attached to the Perron vector.

41 pages, 1 table, and 1 figure. We changed the title and solved the missing case in 2nd version