Constraints on Brouwer's Laplacian spectrum conjecture
| Autor: | Joshua Cooper |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Numerical Analysis
Algebra and Number Theory Conjecture Laplacian spectrum Generalization 010102 general mathematics Complete graph 010103 numerical & computational mathematics 01 natural sciences Upper and lower bounds Combinatorics Bipartite graph Discrete Mathematics and Combinatorics Almost surely Geometry and Topology Split graph 0101 mathematics Mathematics |
| Zdroj: | Linear Algebra and its Applications. 615:11-27 |
| ISSN: | 0024-3795 |
| Popis: | Brouwer's Conjecture states that, for any graph G, the sum of the k largest (combinatorial) Laplacian eigenvalues of G is at most | E ( G ) | + ( k + 1 2 ) , 1 ≤ k ≤ n . We present several interrelated results establishing Brouwer's conjecture for a wide range of graphs G and parameters k. In particular, we show that (1) is true for low-arboricity graphs, and in particular for planar G when k ≥ 11 ; (2) is true whenever the variance of the degree sequence is not very high, generalizing previous results for G regular or random; (3) is true if G belongs to a hereditarily spectrally-bounded class and k is sufficiently large as a function of k, in particular k ≥ 32 n for bipartite graphs; (4) holds unless G has edge-edit distance k 2 n = O ( n 3 / 2 ) from a split graph; (5) no G violates the conjectured upper bound by more than O ( n 5 / 4 ) , and bipartite G by no more than O ( n ) ; and (6) holds for all k outside an interval of length O ( n 3 / 4 ) . Furthermore, we show that a natural generalization of Brouwer's conjecture surprisingly is quite false: asymptotically almost surely, a uniform random signed complete graph violates the conjectured bound by Ω ( n ) . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect