Is the ordered biclique partition number of the complete graph $O(n^{1/2})$? Removing the sub-polynomial term in $bp_{1.5}(K_n)=n^{1/2+o(1)}$

An ordered biclique partition of a graph $G$ is a collection of complete bipartite subgraphs (bicliques) such that every edge is covered at least once and at most twice, and every doubly covered edge has its two endpoints lying in opposite classes in the two covering bicliques; $bp_{1.5}(G)$ denotes the minimum number of bicliques in such a collection. For the complete graph $K_n$, Shigeta and Amano (2015) proved by an explicit construction that $bp_{1.5}(K_n)=n^{1/2+o(1)}$, while Alon's bound on 2-biclique coverings gives $bp_{1.5}(K_n)\ge bp_2(K_n)=\Theta(n^{1/2})$. The open question is whether the sub-polynomial term in the exponent can be eliminated, i.e., whether $bp_{1.5}(K_n)=O(n^{1/2})$ (equivalently $bp_{1.5}(K_n)=\Theta(n^{1/2})$). The two communication-complexity motivations that introduced this parameter — the rank-versus-fooling-set separation for 0/1 matrices and lower bounds on the nondeterministic complexity of the clique-vs-independent-set problem, including the source's harder companion problem of finding a graph with a superpolynomial gap between its chromatic number and its ordered biclique partition number — have all since been resolved, in fact optimally, by other routes (Friesen et al. 2015; Göös 2015; Ben-David et al. 2017; Balodis et al. 2023; Pabbaraju 2026). What survives is a self-contained open extremal question about biclique decompositions of $K_n$: as of August 2026, even the June 2026 generalization to almost-balanced ordered biclique coverings $f(n,k)$ restates the same two-sided bounds $c_1n^{1/2}\le f(n,2)\le c_2n^{1/2+o(1)}$ and leaves the removal of the $o(1)$ open.

Background

A biclique is a complete bipartite graph $B(U,W)$ on vertex classes $U$ and $W$, containing all edges between $U$ and $W$. The biclique partition number $bp(G)$ of a graph $G$ is the minimum number of bicliques whose edge sets partition the edge set of $G$; the classical theorem of Graham and Pollak (1971) states that $bp(K_n)=n-1$ for the complete graph on $n$ vertices. If edges are allowed to be covered up to $t$ times instead of exactly once, one obtains the $t$-biclique covering number $bp_t(G)$, and Alon (1997), through a connection to neighborly families of boxes, proved $bp_2(K_n)=\Theta(n^{1/2})$.

Amano (2014) introduced an intermediate notion motivated by communication complexity. An ordered biclique partition of $G$ is a collection of bicliques $B(U_1,W_1),\dots,B(U_m,W_m)$ such that (i) every edge of $G$ is covered by at least one and at most two bicliques of the collection, and (ii) whenever an edge $\{u,v\}$ is covered by two bicliques $B(U_i,W_i)$ and $B(U_j,W_j)$, the vertex $u$ lies in the first class of one of them and in the second class of the other (formally $(u,v)\in (U_i\times W_i)\cap(W_j\times U_j)$ up to indexing), i.e., the two covering occurrences have opposite orientations. The minimum size of such a collection is $bp_{1.5}(G)$; the subscript marks the interpolation between the 1-covering (partition) number $bp$ and the 2-covering number $bp_2$. An ordinary biclique partition vacuously satisfies the orientation condition, so $bp_2(G)\le bp_{1.5}(G)\le bp(G)$ for every graph.

Two questions about 0/1 matrices and communication motivated this parameter. First, the rank-versus-fooling-set problem: a fooling set for an $n\times n$ 0/1 matrix $M$ is a set $S$ of index pairs all of whose entries share a common value $z$, such that for any two distinct pairs in $S$ at least one of the two cross-entries differs from $z$; fooling-set size $\mathrm{fool}(M)$ lower-bounds nondeterministic communication complexity. Dietzfelbinger, Hromkovič and Schnitger (1996) proved $\mathrm{fool}(M)\le(\mathrm{rank}(M)+1)^2$ over any field and asked whether the exponent 2 is necessary. Second, the clique-vs-independent-set problem (CIS): given a graph $H$ on $N$ vertices, Alice receives a clique of $H$ and Bob an independent set, and they must decide whether the two vertex sets intersect; Yannakakis (1991) gave an $O(\log^2 N)$ protocol for the nondeterministic (equivalently, co-nondeterministic in the complementary formulation) version of this problem. Amano (2014) observed that finding a graph $H$ with chromatic number $\chi(H)\ge f(bp_{1.5}(H))$ is essentially equivalent to exhibiting an explicit CIS instance on $N$ vertices with nondeterministic complexity at least $\log_2 f(N)$ (see also Bousquet, Lagoutte and Thomassé 2014, where $bp_{1.5}$ is denoted $bp_{or}$).

Shigeta and Amano (2015) constructed ordered biclique partitions of the complete graph on the vertex set $[n]^{2k-1}$ of size $O(kn^k)$, i.e., $bp_{1.5}(K_{n^{2k-1}})=O(k n^k)$; letting $k$ grow yields $bp_{1.5}(K_n)=n^{1/2+o(1)}$, improving Amano's earlier $O(n^{2/3})$. Taking $H=K_n$, whose chromatic number is $n$, this gave $n\times n$ 0/1 matrices of rank $n^{1/2+o(1)}$ with fooling sets of size $n$ — a separation $\mathrm{fool}(M)\ge \mathrm{rank}(M)^{2-o(1)}$ — and a $(2-o(1))\log_2 N$ lower bound on the nondeterministic complexity of CIS, matching the best deterministic lower bound of Kushilevitz, Linial and Ostrovsky (1999). On the lower-bound side nothing stronger is known than the trivial borrowing $bp_{1.5}(K_n)\ge bp_2(K_n)=\Theta(n^{1/2})$ from Alon's result. The question is whether the sub-polynomial overhead in the exponent of the Shigeta–Amano construction reflects a real cost of the orientation condition or is merely an artifact of the construction; in the former case the ordered parameter would be asymptotically separated from $bp_2$, and in the latter the correct order is exactly $\Theta(n^{1/2})$.

Problem Statement

Determine whether there exists an absolute constant $C$ such that, for every $n$, the complete graph $K_n$ admits an ordered biclique partition of size at most $Cn^{1/2}$ — that is, whether $bp_{1.5}(K_n)=O(n^{1/2})$, removing the sub-polynomial term in the exponent of the Shigeta–Amano bound $bp_{1.5}(K_n)=n^{1/2+o(1)}$. Since $bp_{1.5}(K_n)\ge bp_2(K_n)=\Theta(n^{1/2})$ by Alon's theorem on 2-biclique coverings, a positive answer is equivalent to $bp_{1.5}(K_n)=\Theta(n^{1/2})$. A negative answer requires proving that for every constant $C$ there are arbitrarily large $n$ with $bp_{1.5}(K_n)>Cn^{1/2}$, which would show that the orientation condition on doubly covered edges intrinsically costs more than a constant factor relative to unconstrained 2-biclique coverings of $K_n$. The harder companion problem posed alongside this question in the source — exhibiting a graph with a superpolynomial gap between its chromatic number and its ordered biclique partition number — has been resolved by later work on the Alon–Saks–Seymour problem and the communication complexity of clique-vs-independent-set and is therefore not part of the open core.

References

1. Shigeta, M., Amano, K. (2015). Ordered biclique partitions and communication complexity problems. Discrete Applied Mathematics 184:248–252. DOI: 10.1016/j.dam.2014.10.029; arXiv:1311.6192. https://arxiv.org/abs/1311.6192
2. Amano, K. (2014). Some improved bounds on communication complexity via new decomposition of cliques. Discrete Applied Mathematics 166:249–254. DOI: 10.1016/j.dam.2013.09.015. https://doi.org/10.1016/j.dam.2013.09.015
3. Graham, R.L., Pollak, H.O. (1971). On the addressing problem for loop switching. Bell System Technical Journal 50(8):2495–2519. DOI: 10.1002/j.1538-7305.1971.tb02618.x. https://doi.org/10.1002/j.1538-7305.1971.tb02618.x
4. Alon, N. (1997). Neighborly families of boxes and bipartite coverings. In: The Mathematics of Paul Erdős II (Algorithms and Combinatorics 14), pp. 27–31. DOI: 10.1007/978-3-642-60406-5_3. https://doi.org/10.1007/978-3-642-60406-5_3
5. Yannakakis, M. (1991). Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences 43(3):441–466. DOI: 10.1016/0022-0000(91)90024-Y. https://doi.org/10.1016/0022-0000(91)90024-Y
6. Dietzfelbinger, M., Hromkovič, J., Schnitger, G. (1996). A comparison of two lower-bound methods for communication complexity. Theoretical Computer Science 168(1):39–51. DOI: 10.1016/S0304-3975(96)00062-X. https://doi.org/10.1016/S0304-3975(96)00062-X
7. Kushilevitz, E., Linial, N., Ostrovsky, R. (1999). The linear-array conjecture in communication complexity is false. Combinatorica 19:241–254. DOI: 10.1007/s004930050054. https://doi.org/10.1007/s004930050054
8. Huang, H., Sudakov, B. (2012). A counterexample to the Alon-Saks-Seymour conjecture and related problems. Combinatorica 32(2):205–219. DOI: 10.1007/s00493-012-2746-4. https://doi.org/10.1007/s00493-012-2746-4
9. Bousquet, N., Lagoutte, A., Thomassé, S. (2014). Clique versus independent set. European Journal of Combinatorics 40:73–92. DOI: 10.1016/j.ejc.2014.02.003. https://doi.org/10.1016/j.ejc.2014.02.003
10. Friesen, M., Hamed, A., Lee, T., Theis, D.O. (2015). Fooling sets and rank. European Journal of Combinatorics 48:143–153. DOI: 10.1016/j.ejc.2015.02.016; arXiv:1208.2920. https://arxiv.org/abs/1208.2920
11. Göös, M. (2015). Lower bounds for clique vs. independent set. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1066–1076. DOI: 10.1109/FOCS.2015.69. https://doi.org/10.1109/FOCS.2015.69
12. Ben-David, S., Hatami, P., Tal, A. (2017). Low-sensitivity functions from unambiguous certificates. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). arXiv:1605.07084. https://arxiv.org/abs/1605.07084
13. Mubayi, D., Vishwanathan, S. (2009). Bipartite coverings and the chromatic number. The Electronic Journal of Combinatorics 16(1):N34. DOI: 10.37236/272. https://doi.org/10.37236/272
14. Balodis, K., Ben-David, S., Göös, M., Jain, S., Kothari, R. (2023). Unambiguous DNFs and Alon–Saks–Seymour. SIAM Journal on Computing (FOCS 2021 version: DOI 10.1109/FOCS52979.2021.00020). DOI: 10.1137/22M1480616; arXiv:2102.08348. https://arxiv.org/abs/2102.08348
15. Fox, J. (2026). A note on the Alon-Saks-Seymour problem. arXiv:2605.28915. https://arxiv.org/abs/2605.28915
16. Babu, A., Ranjan, E., Sai, M.D., Sidhartha, J.N., Suresh, A.I., Vishwas, S. (2026). Almost balanced ordered biclique covering of graphs. arXiv:2606.08506. https://arxiv.org/abs/2606.08506
17. Pabbaraju, C. (2026). Optimal Unambiguous DNFs and Alon-Saks-Seymour. arXiv:2608.02533. https://arxiv.org/abs/2608.02533