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

VL - 84

SP - 45

EP - 52

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -