The de Caen–Gregory–Pritikin conjecture on k-fold biclique partitions of the complete graph, and the extremal constant for clique partitions of complementary graphs

Two exact-value questions in extremal graph theory, both left explicitly open by Rohatgi, Urschel and Wellens (2021) after their asymptotic theorems on clique and biclique partitions. First, a 1993 conjecture of de Caen, Gregory and Pritikin: for every fixed positive integer $k$, is the minimum number $\operatorname{bp}_k(K_n)$ of complete bipartite subgraphs needed to cover every edge of the complete graph $K_n$ exactly $k$ times equal to $n-1$ for all sufficiently large $n$? The lower bound $\operatorname{bp}_k(K_n)\ge n-1$ is classical, the conjecture is verified only for $k\le 18$, and the best general upper bound is $n+2kn^{3/4}+k\sqrt n$. Second, the asymptotic constant $\alpha_\infty=\lim_{n\to\infty} n^{-2}\max_{G} (\operatorname{cp}(G)+\operatorname{cp}(\overline G))$ for the sum of the clique partition numbers of a graph and its complement is known to exist, but is bracketed only between $23/82\approx 0.28049$ and $0.3186$; even its value to within $0.01$ is unknown. The problem asks for both exact answers: prove or refute the eventual equality $\operatorname{bp}_k(K_n)=n-1$, and determine $\alpha_\infty$ exactly.

Background

A biclique is a complete bipartite subgraph. The biclique partition number $\operatorname{bp}(G)$ of a graph $G$ is the minimum number of bicliques whose edge sets partition $E(G)$. The Graham–Pollak theorem (1971), motivated by the addressing problem for loop switching, states that $\operatorname{bp}(K_n)=n-1$: the edges of the complete graph on $n$ vertices can be partitioned into the $n-1$ stars centered at different vertices (a star is a biclique with a single vertex on one side), and an elegant linear-algebraic argument (on the ranks of matrices associated with the bicliques) shows fewer cannot suffice. A natural $k$-fold generalization allows each edge to be covered exactly $k$ times: $\operatorname{bp}_k(G)$ is the minimum size of a collection of bicliques of $G$ such that each edge belongs to exactly $k$ of them, which is equivalent to partitioning the $k$-fold complete multigraph $kK_n$ (every edge with multiplicity $k$) into complete bipartite graphs. The Graham–Pollak rank argument generalizes to give $\operatorname{bp}_k(K_n)\ge n-1$ for all $n$ and $k$. In 1993, de Caen, Gregory and Pritikin conjectured that this bound is tight for large $n$: for every fixed $k$, $\operatorname{bp}_k(K_n)=n-1$ for all sufficiently large $n$. They proved their conjecture for $k\le 18$ using explicit constructions from design theory (families of set systems with prescribed incidence regularity), while for general $k$ the best prior upper bound was $O(kn)$, obtained by compounding small-$k$ constructions. Rohatgi, Urschel and Wellens (2021) proved the asymptotic version $\operatorname{bp}_k(K_n)=(1+o(1))n$: they build a family of $(n,d,t,m)$-designs in the sense of Nisan and Wigderson (families of $n$ subsets of a $d$-element universe, each of size $m$, with pairwise intersections at most $t$; these objects originate in pseudorandomness) with $m=\lfloor k/2\rfloor$ and $t=1$, which yields $d\le k\sqrt n$ bicliques covering every edge of $K_n$ either $2\lfloor k/2\rfloor$ or $2\lfloor k/2\rfloor-2$ times, then use a theorem of Alon giving $\operatorname{bp}_{\{1,2\}}(K_n)\le 2\sqrt n$ (a covering in which each edge is covered once or twice, proved via so-called neighborly families of boxes, i.e. families of axis-aligned boxes in $\mathbb{R}^d$ any two of which intersect in dimension exactly $d-1$) to fix the parity when $k$ is odd, and finally pad with stars. The resulting upper bound is $n+2kn^{3/4}+k\sqrt n$; whether the additive error terms can be removed (i.e., whether the conjecture holds) is open, although Cioabă and Tait showed that the list-covering ingredient cannot be improved in its $n$-dependence, since $\sqrt{n/2}$ bicliques are necessary for a $\{2k-2,2k\}$-covering.

On the clique side, the clique partition number $\operatorname{cp}(G)$ is the minimum number of complete subgraphs (cliques) whose edge sets partition $E(G)$. A classical theorem of Erdős, Goodman and Pósa shows that every $n$-vertex graph satisfies $\operatorname{cp}(G)\le\lfloor n^2/4\rfloor$, with equality for the complete bipartite graph $K_{n/2,n/2}$, which is triangle-free and therefore forces every clique in a partition to be a single edge. In 1986, de Caen, Erdős, Pullman and Wormald studied the sum $\operatorname{cp}(G)+\operatorname{cp}(\overline G)$, where $\overline G$ is the complement of $G$ (the graph on the same vertices with precisely the non-edges of $G$): they proved $\frac{7}{25}n^2+O(n)\le\max_{G}\,(\operatorname{cp}(G)+\operatorname{cp}(\overline G))\le\frac{13}{30}n^2+O(n)$ and conjectured the lower bound $\frac{7}{25}$ to be asymptotically tight. The complementary triangle-packing theorem of Keevash and Sudakov (every graph and its complement contain edge-disjoint collections of $n^2/12.89$ monochromatic triangles under any bicoloring) implies the improved upper bound $0.34481n^2+o(n^2)$, but partitions into triangles and edges cannot beat $0.3\overline 3n^2$ because of $K_{n/2,n/2}$. Rohatgi, Urschel and Wellens disproved the $\frac{7}{25}$ conjecture by modifying the original construction, obtaining self-complementary graphs (graphs isomorphic to their own complements) with $\operatorname{cp}(G)+\operatorname{cp}(\overline G)\ge\frac{23}{82}n^2-O(n)$; on the upper side they studied fractional clique packings (linear-programming relaxations in which cliques may be taken fractionally, which are asymptotically as good as integral packings by a standard rounding theorem), combined a computer search generalizing the Keevash–Sudakov extension method with Ramsey-type blow-up recursions (a blow-up replaces each vertex of a small graph by an independent set of vertices all sharing the same adjacencies to the other parts), and proved $\operatorname{cp}(G)+\operatorname{cp}(\overline G)\le 0.3186n^2+o(n^2)$. Their monotonicity argument also proves that the limit $\alpha_\infty=\lim_{n\to\infty}\frac{1}{n^2}\max_{G\in\mathcal G_n}(\operatorname{cp}(G)+\operatorname{cp}(\overline G))$ exists, so the open question is its exact value. Biclique and clique partition numbers are also connected to lower bounds in communication complexity — the study of how many bits two separated parties must exchange to compute a joint function, where the minimum number of bicliques covering a communication matrix governs nondeterministic complexity — which is part of the classical interest in these quantities.

Problem Statement

The problem consists of two exact-value questions, which ask for the exact forms of the two asymptotic theorems of Rohatgi, Urschel and Wellens (2021); both concern minimum numbers of complete subgraphs or complete bipartite subgraphs covering the edges of graphs.

(A) The de Caen–Gregory–Pritikin conjecture (1993). Prove or disprove: for every positive integer $k$ there exists $N(k)$ such that

$$\operatorname{bp}_k(K_n)=n-1\quad\text{for all }n\ge N(k),$$

where $K_n$ is the complete graph on $n$ vertices and $\operatorname{bp}_k(K_n)$ is the minimum number of bicliques (complete bipartite subgraphs of $K_n$) such that every edge of $K_n$ belongs to exactly $k$ of them. The lower bound $\operatorname{bp}_k(K_n)\ge n-1$ holds for all $n$ and $k$, so an affirmative proof is equivalent to constructing, for each fixed $k$ and all sufficiently large $n$, exactly $n-1$ bicliques covering each edge exactly $k$ times; a disproof must exhibit a fixed $k$ for which $\operatorname{bp}_k(K_n)\ge n$ for infinitely many $n$ (a single finite instance does not refute eventual equality).

(B) The extremal constant for clique partitions of complementary graphs. Determine the exact value of

$$\alpha_\infty=\lim_{n\to\infty}\frac{1}{n^2}\max_{G\in\mathcal G_n}\bigl(\operatorname{cp}(G)+\operatorname{cp}(\overline G)\bigr),$$

whose existence is known. Here, for a graph $G$ on $n$ vertices, $\operatorname{cp}(G)$ is the clique partition number of $G$ (the minimum number of complete subgraphs whose edge sets partition the edge set of $G$), $\overline G$ is the complement of $G$ (the graph on the same vertex set whose edges are exactly the non-edges of $G$), and $\mathcal G_n$ is the set of all graphs on $n$ vertices. The current bracket is $\frac{23}{82}\approx 0.28049\le\alpha_\infty\le 0.3186$, so even determining $\alpha_\infty$ to within $0.01$ is open. The constant $c=\alpha_\infty$ is the common value of the matching lower and upper bounds: a construction family with $\operatorname{cp}(G)+\operatorname{cp}(\overline G)\ge(c-o(1))n^2$, and the bound $\operatorname{cp}(G)+\operatorname{cp}(\overline G)\le(c+o(1))n^2$ for every $n$-vertex graph.

Both components ask for converting the source paper's two asymptotic results — $\operatorname{bp}_k(K_n)=(1+o(1))n$ and $\max_G(\operatorname{cp}(G)+\operatorname{cp}(\overline G))\sim\alpha_\infty n^2$ — into exact answers.

References

1. Dhruv Rohatgi, John C. Urschel, Jake Wellens, 'Regarding two conjectures on clique and biclique partitions', The Electronic Journal of Combinatorics 28(4) (2021) #P4.53, DOI 10.37236/9564, arXiv:2005.02529, https://arxiv.org/abs/2005.02529
2. R. L. Graham, H. O. Pollak, 'On the addressing problem for loop switching', Bell System Technical Journal 50(8) (1971) 2495–2519, DOI 10.1002/j.1538-7305.1971.tb02618.x, https://doi.org/10.1002/j.1538-7305.1971.tb02618.x
3. D. de Caen, D. A. Gregory, D. Pritikin, 'Minimum biclique partitions of the complete multigraph and related designs', in: R. Rees (ed.), Graphs, Matrices, and Designs, Marcel Dekker (1993), pp. 93–120, DOI 10.1201/9780203719916-8, https://doi.org/10.1201/9780203719916-8
4. D. de Caen, P. Erdős, N. J. Pullman, N. C. Wormald, 'Extremal clique coverings of complementary graphs', Combinatorica 6(4) (1986) 309–314, DOI 10.1007/BF02579256, https://doi.org/10.1007/BF02579256
5. P. Erdős, A. W. Goodman, L. Pósa, 'The representation of a graph by set intersections', Canadian Journal of Mathematics 18 (1966) 106–112, DOI 10.4153/cjm-1966-014-3, https://doi.org/10.4153/cjm-1966-014-3
6. S. M. Cioabă, M. Tait, 'Variations on a theme of Graham and Pollak', Discrete Mathematics 313(5) (2013) 665–676, DOI 10.1016/j.disc.2012.12.001, https://doi.org/10.1016/j.disc.2012.12.001
7. P. Keevash, B. Sudakov, 'Packing triangles in a graph and its complement', Journal of Graph Theory 47(3) (2004) 203–216, DOI 10.1002/jgt.20031, https://doi.org/10.1002/jgt.20031
8. N. Alon, 'Neighborly families of boxes and bipartite coverings', in: The Mathematics of Paul Erdős II (Algorithms and Combinatorics 14), Springer (1997), pp. 27–31, DOI 10.1007/978-3-642-60406-5_3, https://doi.org/10.1007/978-3-642-60406-5_3
9. N. Nisan, A. Wigderson, 'Hardness vs randomness', Journal of Computer and System Sciences 49(2) (1994) 149–167, DOI 10.1016/S0022-0000(05)80043-1, https://doi.org/10.1016/S0022-0000(05)80043-1
10. Anand Babu, Sundar Vishwanathan, 'Improved Bounds for Multicovering Hypergraphs', arXiv:2208.12589 (2022), https://arxiv.org/abs/2208.12589
11. Bochuan Lyu, Illya V. Hicks, 'Finding biclique partitions of co-chordal graphs', Discrete Applied Mathematics 337 (2023) 278–287, DOI 10.1016/j.dam.2023.05.001, https://doi.org/10.1016/j.dam.2023.05.001
12. Ting Huang, Jiabao Yang, Yaojun Chen, 'Odd covers for complete graphs and complete 3-graphs', arXiv:2607.07448 (2026), https://arxiv.org/abs/2607.07448
13. Bo Ning, 'On the difference between clique partition and clique covering numbers of graphs', arXiv:2608.11536 (2026), https://arxiv.org/abs/2608.11536
14. Anand Babu, Ervin Ranjan, Maddipati Deshith Sai, Jatla Naga Sidhartha, Anagh Indu Suresh, Sreedhara Vishwas, 'Almost balanced ordered biclique covering of graphs', arXiv:2606.08506 (2026), https://arxiv.org/abs/2606.08506
15. Jarosław Grytczuk, Andrzej P. Kisielewicz, Krzysztof Przesławski, 'Neighborly boxes and bipartite coverings; constructions and conjectures', European Journal of Combinatorics 133 (2026) 104319, DOI 10.1016/j.ejc.2025.104319, arXiv:2402.02199, https://arxiv.org/abs/2402.02199