Supersaturation in Nosal graphs: Triangles and books
Abstract
In this paper, we use the spectral surplus $\lambda(G) - \sqrt{m}$ to measure how far $G$ lies above the Nosal threshold, and prove the following edge-spectral supersaturation results for triangles and books.
(a) Every graph $G$ with $m\ge 3$ edges and $\lambda(G) \ge 1 + \sqrt{m-2}$ contains at least $m-2$ triangles, with equality if and only if $G = K_3 \vee \tfrac{m-3}{3} K_1$. This can be viewed as the third-layer supersaturation in the jump phenomenon, after the first layer $t(G) \ge \lfloor \tfrac{1}{2}(\sqrt{m}-1) \rfloor$ proved by Ning and Zhai, and the second layer $t(G) \ge \tfrac{m-1}{2}$ by Zhang and Zhai.
(b) Every $m$-edge graph $G$ satisfies $t(G) \ge m\bigl(\lambda - \sqrt{m}\,\bigr)$, with equality if and only if $G$ is complete bipartite. Consequently, $\lambda(G) \ge \sqrt{m} + q$ forces $t(G) > q m$ for every real $q > 0$. This is an edge-spectral counterpart of the Lovász--Simonovits theorem, and it improves the Bollobás--Nikiforov bound $t(G) \ge \tfrac13 \lambda(\lambda^2 - m)$ in the range $\sqrt m \le \lambda(G) \le 1.3\sqrt m $.
(c) Every $m$-edge Nosal graph $G$ contains a book of size greater than $\tfrac14 \sqrt{m}$. This improves two recent results on the booksize constant: $\tfrac{1}{24}$ proved by Li, Liu and Zhang, and $\tfrac19$ by Zhai, Li and Lou. This narrows the gap toward the conjectured optimal constant $\tfrac13$.
(d) Every $m$-edge Nosal graph $G$ contains at least $\bigl(\tfrac{1}{8} - o(1)\bigr) m$ copies of the kite $C_4^+=B_2$, and the constant $\tfrac18$ is best possible. This determines the sharp asymptotic constant for counting $C_4^+$ and strengthens the $\Omega(m)$ bound of Li, Liu and Zhang.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요