A new spectral Turán theorem for weighted graphs and consequences
Lele Liu, Bo Ning · 2025
Read A new spectral Turán theorem for weighted graphs and consequences by Lele Liu, Bo Ning (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26410.txt.
Introduction
Lele Liu and Bo Ning prove a new bound in spectral graph theory, the study of networks through the numbers tied to their connection patterns. For a network with no large fully linked group, an older result capped the largest such number, the spectral radius, in terms of the number of links. The pair extend that cap to weighted graphs, where each link carries a weight.
Liu and Ning state the cap as a sum over links, with each link's term set by the largest fully linked group that contains it. They also name all the graphs that hit the cap exactly. From this one result flow several new forms of Turán's theorem and weighted forms of older named results. A key step is a fresh lower bound that balances an upper bound found by others.
Catalog record
| CREATOR | Lele Liu, Bo Ning |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-26410
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A new spectral Turán theorem for weighted graphs and consequences Lele Liu, Bo Ning Abstract Confirming a conjecture of Elphick and Edwards and strengthening a spectral theorem of Wilf, Nikiforov proved that for any K r + 1 K_{r+1} -free graph G G , λ ( G ) 2 ≤ 2 ( 1 − 1 / r ) m \lambda(G)^{2}\leq 2(1-1/r)m , where λ ( G ) \lambda(G) is the spectral radius of G G , and m m is the number of edges of G G . This result was later improved in [ 15 ] , where it was shown that for any graph G G , λ ( G ) 2 ≤ 2 ∑ e ∈ E ( G ) cl ( e ) − 1 cl ( e ) \lambda(G)^{2}\leq 2\sum_{e\in E(G)}\frac{\cl(e)-1}{\cl(e)} , where cl ( e ) \cl(e) denotes the order of the largest clique containing the edge e e . In this paper, we further extend this inequality to weighted graphs, proving that λ ( G ) 2 ≤ 2 ∑ e ∈ E ( G ) cl ( e ) − 1 cl ( e ) w ( e ) 2 , \lambda(G)^{2}\leq 2\sum_{e\in E(G)}\frac{\cl(e)-1}{\cl(e)}w(e)^{2}, and we characterize all extremal graphs attaining this bound. Our main theorem yields several new consequences, including two vertex-based and vertex-degree-based local versions of Turán’s theorem, as well as weighted generalizations of the Edwards–Elphick theorem and the Cvetković theorem, and localized versions of Wilf’s two theorems. Moreover, the result unifies and implies numerous earlier ones from spectral graph theory and extremal graph theory, including Stanley’s spectral inequality, Hong’s inequality, a localized Turán-type theorem, and a recent extremal theorem by Adak and Chandran. Notably, while Nikiforov’s earlier spectral inequality implied Stanley’s bound, it did not imply Hong’s inequality — a gap that is now bridged by our result. As a key tool, we establish the inequality ∑ e ∈ E ( G ) 2 cl ( e ) ≥ n − 1 \sum_{e\in E(G)}\frac{2}{\cl(e)}\geq n-1 , which complements an upper bound ∑ e ∈ E ( G ) 2 cl ( e ) − 1 ≤ n 2 − 2 m \sum_{e\in E(G)}\frac{2}{\cl(e)-1}\leq n^{2}-2m due to Bradač, and Malec and Tompkins, independently. Keywords: Localized spectral Turán problem; Spectral radius; Spectral inequality 1 Introduction A weighted graph G is a triple (V(G),E(G),w) , where V(G) is the vertex set, E(G) is the edge set, and w:E(G)\to\mathbb{R} is a weight function assigning a real value to each edge. When all edge weights are 1 , this reduces to the usual unweighted graph. The adjacency matrix of a weighted graph G on n vertices is the n\times n matrix A(G)=[a_{ij}] , where a_{ij}=w(e) if e=ij\in E(G) , and 0 otherwise. The spectral radius of G , denoted \lambda(G) , is the maximum of the absolute values of the eigenvalues of A(G) . For a matrix M\in\mathbb{R}^{m\times n} , the Frobenius norm of M=[m_{ij}] is defined as \|M\|_{F}:=\big(\sum_{i=1}^{m}\sum_{j=1}^{n}m_{ij}^{2}\big)^{1/2} . Let A=[a_{ij}] and B=[b_{ij}] be two matrices of the same dimensions. The Hadamard product A\circ B of A and B is defined via element-wise multiplication: (A\circ B)_{ij}=a_{ij}b_{ij} . For a subset S\subseteq[n]:=\{1,2,\ldots,n\} , the characteristic vector of S is the vector \bm{1}_{S}\in\{0,1\}^{n} whose i -th entry is 1 if i\in S and 0 otherwise. For a weighted graph G and an edge e\in E(G) , let \cl_{G}(e) (or \cl(e) in short) denote the order of the largest clique containing e . Our main theorem is the following. Theorem 1.1 . Let G be a weighted graph with edge weight w(e) for each edge e . Then \lambda(G)\leq\sqrt{2\sum_{e\in E(G)}\frac{\cl(e)-1}{\cl(e)}w(e)^{2}}. (1.1) Equality holds if and only if G is, up to isolated vertices, a complete r -partite graph for some r ( with partition V_{1}\cup V_{2}\cup\cdots\cup V_{r} ) , and there exists a vector \bm{w}\in\mathbb{R}^{n} such that (1) A(G)=\pm\sum_{i=1}^{r}(\bm{1}_{V_{i}}\circ\bm{w})\big((\bm{1}-\bm{1}_{V_{i}})\circ\bm{w}\big)^{\mathrm{T}} ; and (2) \|\bm{1}_{V_{i}}\circ\bm{w}\|^{2}=\|\bm{w}\|^{2}-\sqrt{1-1/r}\cdot\|A(G)\|_{F} for each i\in[r] . We now present an example to clarify the conditions for equality in ( 1.1 ). Example 1.1 . Consider the weighted complete 3 -partite graph G with vertex classes V_{1}=\{v_{1}\} , V_{2}=\{v_{2},v_{3}\} , and V_{3}=\{v_{4},v_{5}\} . The edge weights are indicated by the numbers on the edges (see Figure 1 ). v_{1} v_{2} v_{5} v_{4} v_{3} 1 \sqrt{2} \sqrt{6}/2 \sqrt{6}/2 \sqrt{2}/2 \sqrt{2}/2 1 1 Figure 1: The graph in Example 1.1 According to Theorem 1.1 , the spectral radius of G is at most 2\sqrt{3} . We will demonstrate that this upper bound is actually achieved, proving \lambda(G)=2\sqrt{3} . Set \bm{w}=\sqrt[4]{3}(1,\sqrt{3}/3,\sqrt{6}/3,\sqrt{2}/2,\sqrt{2}/2)^{\mathrm{T}} . One can directly verify that \bm{w} satisfies item (1). Moreover, \|\bm{w}\|^{2}=3\sqrt{3} , \|A(G)\|_{F}=3\sqrt{2} , and \|\bm{1}_{V_{i}}\circ\bm{w}\|^{2}=\sqrt{3}=\|\bm{w}\|^{2}-\sqrt{2/3}\cdot\|A(G)\|_{F} for i\in[3] . Thus, by Theorem 1.1 , we conclude that \lambda(G)=2\sqrt{3} . The original motivation of the above inequality is the following problem. Problem 1.1 . Is there an extremal result on weighted graphs which implies Bradač’s Theorem (i.e., a localized version of Turán Theorem, see Corollary 2.1 )? A weaker result regarding Problem 1.1 can be found in [ 15 ] . Corollary 1.1 ( [ 15 ] ) . Let G be a graph with spectral radius \lambda(G) . Then \lambda(G)\leq\sqrt{2\sum_{e\in E(G)}\frac{\cl(e)-1}{\cl(e)}}. (1.2) Equality holds if and only if G is a complete bipartite graph for \omega=2 , or a complete regular \omega -partite graph for \omega\geq 3 ( possibly with some isolated vertices ) . We emphasize that extending the above result to weighted graphs is essential, as it allows our new result to encompass Bradač’s extremal theorem and some of the following results — something our previous result (Corollary 1.1 ) could not achieve. There are also similar phenomenons supporting this idea. For example, Li and Ning [ 14 ] showed that the classic Frieze-McDiarmid-Reed Theorem [ 11 ] on paths and Bondy-Fan Theorem [ 4 ] on cycles in weighted graphs imply Malec-Tompkins Theorem [ 16 ] on paths, and Zhao-Zhang Theorem [ 24 ] on cycles in terms of localized versions, and surely derive shorts proofs. Theorem 1.1 unifies a series of previous results on upper bounds of spectral radius and new ones, and also some results from extremal graph theory. It should be mentioned that Nikiforov’s inequality (Corollary 2.5 ) can imply Stanley’s inequality (Corollary 2.3 ) via Turán’s theorem (see [ 19 ] ), our result offers a broader scope. Specifically, our inequality implies Hong’s inequality (Corollary 2.4 ) and some new spectral inequalities, and leads to some new theorems in extremal graph theory. For example, we derive the following theorem: Theorem 1.2 . Let G be a graph on n\geq 2 vertices with no isolated vertices. Then \sum_{e\in E(G)}\frac{1}{\cl(e)-1}\geq\frac{n}{2}, (1.3) and \sum_{e\in E(G)}\frac{1}{\cl(e)}\geq\frac{n-c(G)}{2}, (1.4) where c(G) is the number of connected components of G . Answering an open problem proposed by Balogh and Lidicky at the Combinatorics, Probability and Computing conference held in Oberwolfach in 2022, Bradač [ 6 ] established the inequality \sum_{e\in E(G)}\frac{1}{\cl(e)-1}\leq\frac{n^{2}}{2}-m. Malec and Tompkins [ 16 ] proved this result by induction method, independently. Our result above complements with the upper bound established independently by Bradač [ 6 ] , and Malec and Tompkins [