More on the Bipartite Decomposition of Random Graphs. Issue 1 (22nd February 2016)

• Record Type: Journal Article
• Authors: Alon, Noga; Bohman, Tom; Huang, Hao
• Is Part Of: Journal of graph theory. Volume 84:Issue 1(2017)
• Page Start: 45
• Page End: 52
• Publication Date: 2016-02-22
• Subjects: bipartite decomposition -- random graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22010
• Languages: English
• ISSNs: 0364-9024

Abstract

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.