Bollobás-Nikiforov conjecture holds asymptotically almost surely
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913646174535680 |
|---|---|
| author | Liu, Chunmeng Bu, Changjiang |
| author_facet | Liu, Chunmeng Bu, Changjiang |
| contents | Bollobás and Nikiforov (J. Combin. Theory Ser. B. 97 (2007) 859-865) conjectured that for a graph $G$ with $e(G)$ edges and the clique number $ω(G)$, then $
λ_{1}^{2}+λ_{2}^{2}\leq 2e(G)\left(1-\frac{1}{ω(G)}\right), $ where $λ_{1}$ and $λ_{2}$ are the largest and the second largest eigenvalues of the adjacency matrix of $G$, respectively. In this paper, we prove that for a sequence of random graphs the conjecture holds true with probability tending to one as the number of vertices tends to infinity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07137 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bollobás-Nikiforov conjecture holds asymptotically almost surely Liu, Chunmeng Bu, Changjiang Combinatorics 05C50, 15B52 Bollobás and Nikiforov (J. Combin. Theory Ser. B. 97 (2007) 859-865) conjectured that for a graph $G$ with $e(G)$ edges and the clique number $ω(G)$, then $ λ_{1}^{2}+λ_{2}^{2}\leq 2e(G)\left(1-\frac{1}{ω(G)}\right), $ where $λ_{1}$ and $λ_{2}$ are the largest and the second largest eigenvalues of the adjacency matrix of $G$, respectively. In this paper, we prove that for a sequence of random graphs the conjecture holds true with probability tending to one as the number of vertices tends to infinity. |
| title | Bollobás-Nikiforov conjecture holds asymptotically almost surely |
| topic | Combinatorics 05C50, 15B52 |
| url | https://arxiv.org/abs/2501.07137 |