TY - JOUR
T1 - More on the Bipartite Decomposition of Random Graphs
AU - Alon, Noga
AU - Bohman, Tom
AU - Huang, Hao
N1 - Funding Information:
Part of this work was done during the workshop on Probabilistic and Extremal Combinatorics which took place in IMA, Minneapolis in September, 2014. We would like to thank IMA and the organizers of the conference for their hospitality. We also thank Pat Devlin and Jeff Kahn for a helpful conversation. We also would like to thank Kevin Vander Meulen for pointing out that Theorem is a special case of their result proved earlier in.
Publisher Copyright:
© 2016 Wiley Periodicals, Inc.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - 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.
AB - 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.
KW - bipartite decomposition
KW - random graph
UR - http://www.scopus.com/inward/record.url?scp=84959200524&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84959200524&partnerID=8YFLogxK
U2 - 10.1002/jgt.22010
DO - 10.1002/jgt.22010
M3 - Article
AN - SCOPUS:84959200524
SN - 0364-9024
VL - 84
SP - 45
EP - 52
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 1
ER -