2014/09/22 by Noga Alon, Tom Bohman, Alon, Noga +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1409.6165
openalex publication_date 2014/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G=(V,E), let bc(G) denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G, bc(G) ≤ n -α(G), where α(G) is the maximum size of an independent set of G. Erdős conjectured in the 80s that for almost every graph G equality holds, i.e., that for the random graph G(n,0.5), bc(G)=n-α(G) with high probability, that is, with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for G=G(n,0.5), bc(G) ≤ n-α(G)-1 with high probability. We prove a stronger bound: there exists an absolute constant c>0 so that bc(G) ≤ n-(1+c)α(G) with high probability.