کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656785 | 1632980 | 2015 | 16 صفحه PDF | دانلود رایگان |
For a graph G=(V,E)G=(V,E), let τ(G)τ(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 , τ(G)≤n−α(G)τ(G)≤n−α(G), where α(G)α(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, i.e., that for the random graph G(n,0.5)G(n,0.5), τ(G)=n−α(G)τ(G)=n−α(G) with high probability, that is, with probability that tends to 1 as n tends to infinity. Here we show that this conjecture is (slightly) false, proving that for all n in a subset of density 1 in the integers and for G=G(n,0.5)G=G(n,0.5), τ(G)≤n−α(G)−1τ(G)≤n−α(G)−1 with high probability, and that for some sequences of values of n tending to infinity τ(G)≤n−α(G)−2τ(G)≤n−α(G)−2 with probability bounded away from 0. We also study the typical value of τ(G)τ(G) for random graphs G=G(n,p)G=G(n,p) with p<0.5p<0.5 and show that there is an absolute positive constant c so that for all p≤cp≤c and for G=G(n,p)G=G(n,p), τ(G)=n−Θ(α(G))τ(G)=n−Θ(α(G)) with high probability.
Journal: Journal of Combinatorial Theory, Series B - Volume 113, July 2015, Pages 220–235