کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656785 1632980 2015 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bipartite decomposition of random graphs
ترجمه فارسی عنوان
تجزیه دو طرفه گرافهای تصادفی
کلمات کلیدی
تجزیه دو طرفه، نمودار تصادفی روش استفن چن
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 113, July 2015, Pages 220–235
نویسندگان
,