Brouwer's conjecture holds asymptotically almost surely

DOI10.1016/J.LAA.2020.03.019MaRDI QIDQ2174101zbMATH OpenOpenAlexWikidataFDO

Authors Israel Rocha

Publication date 17 April 2020

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.05368

zbMATH Keywords

Brouwer's conjecturerandom Laplacian matrix

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eigenvalues, singular values, and eigenvectors (15A18) Signed and weighted graphs (05C22)

Abstract: We show that for a sequence of random graphs Brouwer's conjecture holds true with probability tending to one as the number of vertices tends to infinity. Surprisingly, it was found that a similar statement holds true for weighted graphs with possible negative weights as well. For graphs with a fixed number of vertices, the result implies that there are constants $C>0$ and $n_0$ such that if $ngeq{n}_0$ then among all $2^{nchoose2}$ graphs with $n$ vertices, at least $left(1-expleft(-Cnight)ight)2^{nchoose2}$ graphs satisfy Brouwer's conjecture.

Recommendations

• Constraints on Brouwer's Laplacian spectrum conjecture
• On Brouwer's conjecture for the sum of \(k\) largest Laplacian eigenvalues of graphs
• On Laplacian eigenvalues of graphs and Brouwer's conjecture
• The union-closed sets conjecture almost holds for almost all random bipartite graphs
• The union-closed sets conjecture almost holds for almost all random bipartite graphs

Cites work

• Spectra of graphs
• Spectral distributions of adjacency and Laplacian matrices of random graphs

Cited in

(3)

• Partial sum of eigenvalues of random graphs.
• Brouwer's conjecture for the Cartesian product of graphs
• The Cerny Conjecture Holds with High Probability

This page was built for publication: Brouwer's conjecture holds asymptotically almost surely

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174101)