Abstract
For a graph $G=(V,E)$, let $bc(G)$ denote the minimum number of pairwise edge-disjoint complete bipartite subgraphs (bicliques) required to partition the edges of $G$. While it is well-established that $bc(G) \leq n - \alpha(G)$, where $\alpha(G)$ is the size of the maximum independent set, Paul Erdős conjectured in the 1980s that equality holds for almost all graphs. This paper refutes that conjecture for the random graph $G(n, 0.5)$, demonstrating that $bc(G) \leq n - (1+c)\alpha(G)$ for some absolute constant $c > 0$.
Introduction
The study of biclique partitions originated with the Graham-Pollak theorem (1971), which states that the complete graph $K_n$ requires exactly $n-1$ bicliques to partition its edges. For a general graph $G$, a trivial upper bound is $bc(G) \leq n - \alpha(G)$. This is achieved by taking a maximum independent set $S$ and, for every vertex $v \in V \setminus S$, forming a "star" (a specific type of biclique) consisting of all edges incident to $v$ that have not been covered by previous stars.
In the 1980s, Paul Erdős conjectured that for the Erdős-Rényi random graph $G(n, 0.5)$, this star-based construction is optimal, meaning $bc(G) = n - \alpha(G)$ with high probability. While previous work by Noga Alon showed this was strictly false by a small constant, the magnitude of the gap remained an open question until this work.
Methodology
The authors utilize the probabilistic method, specifically the second moment method, to establish a significantly stronger upper bound. The proof strategy relies on identifying specific induced subgraphs that allow for more efficient edge coverage than the standard star decomposition.
Structural Construction
The researchers define a family of bipartite graphs, denoted as $\mathcal{F}_k$, which possess a small biclique partition number relative to their order. By proving that $G(n, 0.5)$ contains one of these special bipartite graphs as an induced subgraph with high probability, they demonstrate that one can "save" more than one biclique per vertex compared to the trivial bound.
Three-Stage Exposure
To provide a simpler proof for a weaker (but still significant) improvement of $\Omega(\log \log n)$, the authors employ a "three-stage exposure" technique. By revealing the edges of the random graph in logical steps—edges within a specific set, edges between sets, and edges within a final set—they identify pairs of vertices with identical neighborhoods. This application of the "Birthday Paradox" logic allows for the merging of stars, thereby reducing the total count of bicliques needed.
Key Results
The primary contribution of this work is the proof that there exists an absolute constant $c > 0$ such that: $$bc(G) \leq n - (1+c)\alpha(G)$$ with high probability for $G \sim G(n, 0.5)$.
Given that the size of the maximum independent set $\alpha(G)$ for such graphs is approximately $2 \log_2 n$, the authors provide a quantitative improvement, showing: $$bc(G) \leq n - 2.015 \log_2 n$$ This result represents a significant departure from the Erdős conjecture and the previous best bounds which were closer to $n - 2 \log_2 n$.
Additionally, the paper establishes a tight bound for "twin-free" graphs (graphs where no two vertices share the same set of neighbors). They prove that a twin-free graph with $bc(G) = r$ can have at most $2^{r+1} - 1$ vertices, linking the decomposition number directly to the maximum possible unique structural information a graph can hold.
Discussion and Future Work
While this paper provides a definitive refutation of the Erdős conjecture for $p = 0.5$, several questions remain. The authors did not attempt to optimize the constant $c$, suggesting that the bound could potentially be lowered further.
Furthermore, the current methodology does not yield improvements for sparse random graphs where $p < 0.5$. It remains possible that the Erdős conjecture holds true in these sparser regimes. The ultimate limit of $bc(G)$—whether it is $n - \Theta(\alpha(G))$ or if an even smaller bound exists—remains a compelling open problem in extremal graph theory.
Reference: Alon, N., Bohman, T., & Huang, H. (2014). More on the bipartite decomposition of random graphs. arXiv:1409.6165v1 [math.CO].
Summary updated