Abstract
For a graph $G$, let $cp(G)$ denote the minimum number of cliques of $G$ needed to cover the edges of $G$ exactly once. Similarly, let $bp_k(G)$ denote the minimum number of bicliques (i.e. complete bipartite subgraphs of $G$) needed to cover each edge of $G$ exactly $k$ times. We consider two conjectures – one regarding the maximum possible value of $cp(G) + cp(\overline{G})$ (due to de Caen, Erdős, Pullman and Wormald) and the other regarding $bp_k(K_n)$ (due to de Caen, Gregory and Pritikin). We disprove the first, obtaining improved lower and upper bounds on $\max_G cp(G) + cp(\overline{G})$, and we prove an asymptotic version of the second, showing that $bp_k(K_n) = (1+o(1))n$.
Introduction
This paper addresses two long-standing open questions in extremal graph theory concerning edge partitions. The first problem focuses on biclique $k$-covers. A foundational result by Graham and Pollak (1971) established that exactly $n-1$ bicliques are required to partition the edges of a complete graph $K_n$. A 1993 conjecture proposed that this requirement of $n-1$ bicliques persists even when every edge must be covered exactly $k$ times.
The second problem investigates complementary clique partitions. For any graph $G$, $cp(G)$ is the minimum number of cliques needed to partition its edges. The authors seek to determine the maximum possible value of $cp(G) + cp(\overline{G})$ for graphs on $n$ vertices. Since 1986, a significant gap has existed between the known upper and lower bounds for this "worst-case" scenario involving a graph and its complement.
Methodology
The authors employ a multifaceted approach combining combinatorial construction with computational optimization:
- Combinatorial Designs: To address the biclique problem, they utilize designs inspired by Nisan and Wigderson to construct biclique families that cover edges nearly $k$ times.
- Padding and Correction: Any discrepancies in edge coverage are resolved using "stars" (a simple biclique type) centered at each vertex, ensuring exact $k$-fold coverage without significantly increasing the total count.
- Fractional Relaxation: The integer clique partition problem is relaxed into a fractional version, transforming a difficult combinatorial task into a linear programming (LP) problem.
- Computer-Aided Search: The authors implemented the "KS extension method" to numerically solve these LPs for all non-isomorphic graphs up to $n=19$ vertices, providing a solid numerical foundation for their asymptotic bounds.
- Ramsey Theory: Averaging lemmas and Ramsey-type arguments are used to extend results from small graphs to large-scale asymptotic bounds by guaranteeing the existence of monochromatic cliques.
Key Insights and Constructions
A primary insight of the paper is the asymptotic tightness of the biclique conjecture. While the exact value of $n-1$ remains difficult to prove, the authors demonstrate that the leading order term is indeed $n$. Their construction proves that a "mostly correct" cover can be efficiently patched with a linear number of stars.
In the realm of clique partitioning, the authors utilize self-complementary graph constructions to balance the partition numbers between $G$ and $\overline{G}$. The $H_\ell(G)$ construction is central to establishing new lower bounds for the maximum total clique partition number.
Results
The authors provide significant improvements to the bounds of both problems:
- Biclique $k$-covers: They prove that $bp_k(K_n) = (1 + o(1))n$. Specifically, they provide a construction using at most $n + 2kn^{3/4} + k\sqrt{n}$ bicliques, confirming the conjecture's asymptotic validity.
- Clique Partitions: The constant $c$ in the asymptotic maximum $\max (cp(G) + cp(\overline{G})) \sim cn^2$ is significantly narrowed. The lower bound was improved from $0.28$ to $23/82 \approx 0.2805$, while the upper bound was reduced from $0.3448$ to $0.3186$.
Conclusion
This work resolves the asymptotic version of the biclique $k$-cover conjecture and provides the tightest known bounds for complementary clique partitions. While the exact version of the biclique conjecture ($bp_k(K_n) = n-1$ exactly) remains open, the authors' use of fractional relaxation and computer-aided search sets a new standard for approaching these problems. Future work may close the remaining gaps through more sophisticated self-complementary constructions or expanded numerical searches.
Summary updated