Decomposition of random graphs into complete bipartite graphs

DOI10.1137/140960888MaRDI QIDQ5744698zbMATH OpenOpenAlexFDO

Authors Xing Peng, Fan Chung

Publication date 19 February 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.0860

zbMATH Keywords

bipartition numberdecompositionrandom graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We consider the problem of partitioning the edge set of a graph $G$ into the minimum number $au(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 $au(G)$ is between $n-c(l{n}_{1/p}n{)}^{3+epsilon}$ and $n-2l{n}_{1/(1-p)}n$ for any positive constants $c$ and $epsilon$.

Recommendations

• Bipartite decomposition of random graphs
• scientific article; zbMATH DE number 3841905
• More on the bipartite decomposition of random graphs
• Covering a graph by complete bipartite graphs
• On the decomposition of random hypergraphs

Cites work

• A counting proof of the Graham-Pollak theorem
• A new proof of a theorem of Graham and Pollak
• A note on an inequality involving the normal distribution
• A polynomial space proof of the Graham-Pollak theorem
• A simple proof of Graham and Pollak's theorem
• Bipartite decomposition of random graphs
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• More on the bipartite decomposition of random graphs
• On colouring random graphs
• On the Addressing Problem for Loop Switching
• On the decomposition ofkn into complete bipartite graphs
• Reducibility among combinatorial problems
• Some remarks on the theory of graphs
• Weighted sums of certain dependent random variables

Cited in

(15)

• Decomposition of product graphs into complete bipartite subgraphs
• Covering a graph by complete bipartite graphs
• Probabilistic methods for decomposition dimension of graphs
• Addressing graph products and distance-regular graphs
• On rainbow-cycle-forbidding edge colorings of finite graphs
• Bipartite decomposition of random graphs
• More on the bipartite decomposition of random graphs
• scientific article; zbMATH DE number 3841905 (Why is no real title available?)
• Decomposition of an infinite complete graph into complete bipartite subgraphs
• scientific article; zbMATH DE number 5287650 (Why is no real title available?)
• scientific article; zbMATH DE number 1933236 (Why is no real title available?)
• Decomposing almost complete graphs by random trees
• A critical probability for biclique partition of \(G_{n,p}\)
• On the decomposition of random hypergraphs
• On the decomposition of graphs into complete bipartite graphs

This page was built for publication: Decomposition of random graphs into complete bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5744698)