More on the Bipartite Decomposition of Random Graphs

详细信息    查看全文

• 作者：Noga Alon ; Tom Bohman and Hao Huang
• 刊名：Journal of Graph Theory
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：84
• 期：1
• 页码：45-52
• 全文大小：109K
• ISSN：1097-0118

文摘

For a graph G=(V,E), let bp(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, bp(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), bp(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), bp(G)≤n−α(G)−1 with high probability. We prove a stronger bound: there exists an absolute constant c>0 so that bp(G)≤n−(1+c)α(G) with high probability.