2014/02/26 by Noga Alon, Alon, Noga
Mathematics · #05C80 #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.1402.6466
openalex publication_date 2014/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G=(V,E), let τ(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, τ(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), τ(G)=n-α(G) with high probability, that is, with probability that tends to 1 as n tends to infinity. Here we show that this conjecture is (slightly) false, proving that for most values of n tending to infinity and for G=G(n,0.5), τ(G) ≤ n-α(G)-1 with high probability, and that for some sequences of values of n tending to infinity τ(G) ≤ n-α(G)-2 with probability bounded away from 0. We also study the typical value of τ(G) for random graphs G=G(n,p) with p < 0.5 and show that there is an absolute positive constant c so that for all p ≤ c and for G=G(n,p), τ(G)=n-Θ(α(G)) with high probability.