More on the Bipartite Decomposition of Random Graphs. Issue 1 (22nd February 2016) - Alon, Noga
Abstract: For a graph G = ( V, E ), let b p ( 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, b p ( 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, that is that for the random graph G ( n, 0.5 ), b p ( 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 ), b p ( G ) ≤ n − α ( G ) − 1 with high probability. We prove a stronger bound: there exists an absolute constant c > 0 so that b p ( G ) ≤ n − ( 1 + c ) α ( G ) with high probability.