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

decompositionrandom graphsbipartition number

Mathematics Subject Classification ID

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

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

(14)

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

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)