A critical probability for biclique partition of G_n,p

DOI10.1016/J.JCTB.2023.12.005arXiv2206.13490WikidataQ130132461 ScholiaQ130132461MaRDI QIDQ6196153FDOQ6196153

Authors: Tom Bohman, Jakob Hofstad 

Publication date: 14 March 2024

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: The biclique partition number of a graph $G=(V,E)$, denoted $bp(G)$, is 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 $bp(G)leqn-alpha(G)$, where $alpha(G)$ is the maximum size of an independent set of $G$. ErdH{o}s conjectured in the 80's that for almost every graph $G$ equality holds; i.e., if $G=G_{n,1/2}$ then $bp(G)=n-alpha(G)$ with high probability. Alon showed that this is false. We show that the conjecture of ErdH{o}s is true if we instead take $G=G_{n,p}$, where $p$ is constant and less than a certain threshold value $p_{0}approx0.312$. This verifies a conjecture of Chung and Peng for these values of $p$. We also show that, if $p_0<p<1/2$, then $bp(G_{n,p})=n-(1+Theta(1))alpha(G_{n,p})$ with high probability.

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

zbMATH Keywords

random graphgraph decomposition

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Title not available (Why is that?)
• On the Addressing Problem for Loop Switching
• Paths in graphs
• The probabilistic method
• Cliques in random graphs
• Proof of the Van den Berg–Kesten Conjecture
• Title not available (Why is that?)
• Introduction to Random Graphs
• Inequalities with applications to percolation and reliability
• On the decomposition ofkn into complete bipartite graphs
• A polynomial space proof of the Graham-Pollak theorem
• A new proof of a theorem of Graham and Pollak
• Bipartite decomposition of random graphs
• More on the Bipartite Decomposition of Random Graphs
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• Decomposition of Random Graphs into Complete Bipartite Graphs
• Some People Have All the Luck
• The van den Berg-Kesten-Reimer operator and inequality for infinite spaces

This page was built for publication: A critical probability for biclique partition of \(G_{n,p}\)

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