TL;DR
This paper refines an upper bound on the minimum number of complete bipartite subgraphs needed to cover all edges of a random graph. The authors prove that for a random graph $G(n, 0.5)$, this number is strictly less than $n - (1+c)\alpha(G)$ with high probability, improving on previous results and getting closer to a long-standing conjecture.
What Problem Does This Paper Address?
The paper delves into the problem of "bipartite decomposition" of graphs. Specifically, it focuses on finding the minimum number of complete bipartite subgraphs (also called bicliques) that can perfectly cover all edges of a given graph $G$. This minimum number is denoted by $bc(G)$. A famous result by Graham and Pollak states that for a complete graph $K_n$, $bc(K_n) = n-1$.
A key question in this area, posed by Erdős, is about the behavior of $bc(G)$ for random graphs, particularly $G(n, 0.5)$ (a graph where each edge exists independently with probability 0.5). Erdős conjectured that for almost all such graphs, $bc(G) = n - \alpha(G)$ with high probability, where $\alpha(G)$ is the size of the largest independent set in $G$. However, previous work by the first author showed this conjecture to be slightly false. This paper aims to provide a tighter upper bound on $bc(G)$ for random graphs, moving beyond the $n - \alpha(G)$ bound.
Methods
The paper employs two main approaches to establish its results:
- Second Moment Method: For the main theorem (Theorem 1.1), the authors use the second moment method to estimate the probability that a specific type of induced subgraph appears in a random graph. They define a family of graphs $F_k$ with certain structural properties (related to bipartite decomposition and independent sets) and then count how many such induced subgraphs exist in $G(n, 0.5)$. By analyzing the expectation and variance of the count of these induced subgraphs, they show that a graph with the desired properties appears with high probability. This, in turn, leads to the improved upper bound on $bc(G)$.
- Three-Stage Exposure and Birthday Paradox: A simpler, albeit weaker, result (inequality (1)) is proven using a "three-stage exposure" of the random graph's edges. The edges are revealed in three stages: within a partition of vertices, between the partitions, and then again within the second partition. This method leverages a probabilistic argument related to the "birthday paradox" to show that certain pairs of vertices are likely to have the same neighborhood in a specific subset of vertices. This allows for a decomposition into bicliques and stars, yielding the bound $bc(G) \leq n - \alpha(G) - \Omega(\log \log n)$.
Datasets
Not discussed in the paper. The paper deals with theoretical properties of random graphs, not empirical evaluation on specific datasets.
Key Insights and Ideas
- Erdős' Conjecture is (Slightly) False: The paper builds on the finding that the exact equality $bc(G) = n - \alpha(G)$ for random graphs is not quite true. This paper refines the upper bound, suggesting a more nuanced relationship.
- The Power of Induced Subgraphs: The proof of the main theorem cleverly uses the existence of specific induced subgraphs to constrain the bipartite decomposition of the entire graph. If a random graph contains a particular structure, it implies limitations on how its edges can be decomposed.
- Birthday Paradox for Graph Structure: The simpler proof elegantly uses the birthday paradox to argue that certain vertices are likely to share neighborhoods, which is crucial for constructing the bipartite decomposition. This highlights how seemingly unrelated probabilistic phenomena can have direct applications in graph theory.
- Focus on the Constant: The paper emphasizes that the main result achieves the best possible bound "up to the constant c," suggesting that the quantitative improvement is significant, even if the asymptotic form of the bound is similar to previous ones.
Key Results
- Theorem 1.1: For a random graph $G = G(n, 0.5)$, there exists an absolute constant $c > 0$ such that $bc(G) \leq n - (1 + c)\alpha(G)$ with high probability. This is a significant improvement over previous bounds, getting closer to the conjectured $n - \alpha(G)$ form.
- Inequality (1): A simpler proof yields $bc(G) \leq n - \alpha(G) - \Omega(\log \log n)$ with high probability for $G = G(n, 0.5)$. While weaker than Theorem 1.1, it's presented as an interesting result in its own right.
- Twin-Free Graphs: The paper also presents a result on twin-free graphs (graphs where no two vertices have identical neighborhoods), showing that such a graph with a biclique decomposition into $r$ bicliques has at most $2^{r+1}-1$ vertices, and this bound is tight.
Limitations and Future Work
- The Constant 'c': The authors acknowledge that their main result is "up to the constant c." Optimizing this constant is a potential area for future work.
- Deciding $n - O(\alpha(G))$: It remains an open question whether $bc(G) = n - O(\alpha(G))$ holds with high probability for random graphs. The current results provide a tighter bound but don't fully resolve this.
- General Random Graphs $G(n,p)$: For $p < 0.5$, the paper notes that their proofs do not offer improvements over the trivial $bc(G) \leq n - \alpha(G)$ bound. It's an open question whether $bc(G) = n - \alpha(G)$ holds for any fixed $p < 0.5$.
- Twin-Free Graphs: The result on twin-free graphs is a specific theoretical result. Its broader implications or connections to other graph properties could be explored further.
Summary updated