Brouwer's conjecture holds asymptotically almost surely

2019/06/12 by Israel Rocha, Rocha, Israel · 2 citations
Mathematics · #05C50 #15A18 #15A52 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C50 #msc:15A18 #msc:15A52

paper · pdf · doi:10.48550/arxiv.1906.05368

arxiv created 2019/06/12 · arxiv updated 2019/06/14

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₀ such that if n≥ n₀ then among all 2^{n \choose 2} graphs with n vertices, at least (1-exp(-Cn))2^{n \choose 2} graphs satisfy Brouwer's conjecture.

Cited by

• Remarks on the Brouwer Conjecture
• Sums of Laplacian eigenvalues and sums of degrees

Related

• Proof of Brouwers Conjecture (BC) for all graphs with number of vertices n > n₀ assuming that BC holds for n< n₀ for some n₀
• Constraints on Brouwer's Laplacian Spectrum Conjecture
• More on the full Brouwer Laplacian spectrum conjecture
• Remarks on the Brouwer Conjecture
• The 1-2-3 Conjecture holds for graphs with large enough minimum degree