Decomposition of random graphs into complete bipartite graphs

الأصل · EN

We consider the problem of partitioning the edge set of a graph G into the minimum number τ(G) of edge-disjoint complete bipartite subgraphs. We show that for a random graph G in G(n,p), for p is a constant no greater than 1/2, almost surely τ(G) is between n- c(₁/ₚ n)³⁺ε and n - 2₁/₍₁₋ₚ₎ n for any positive constants c and ε.