Biclique Partition Numbers of Random Graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph. Under the convention that a complete bipartite graph has two nonempty parts, a biclique subgraph of $G$ consists of disjoint nonempty sets $A,B\subseteq V$ together with all edges joining $A$ to $B$. Such a subgraph need not be induced: edges of $G$ within either part are irrelevant to its use in an edge partition. Define \[ \tau(G)=\min\left\{k\geq 0:E(G)=\bigsqcup_{i=1}^{k}E(H_i),\quad H_i\subseteq G\text{ is a complete bipartite subgraph}\right\}. \] Thus the subgraphs may share vertices, but their edge sets are disjoint, and $\tau(G)=0$ when $E(G)=\varnothing$.

For a graph with at least one edge, define the largest order of an induced complete bipartite subgraph by \[ \beta(G)=\max\left\{|A|+|B|:\begin{array}{l} A,B\subseteq V,\quad A\cap B=\varnothing,\quad A,B\ne\varnothing,\\ E(G[A\cup B])=\{\{a,b\}:a\in A,\ b\in B\} \end{array}\right\}. \] Here order means the total number of vertices in both parts.

Let $G_n\sim G(n,1/2)$, meaning that $V(G_n)=\{1,\ldots,n\}$ and each unordered pair of distinct vertices is an edge independently with probability $1/2$. Under the nonempty-parts convention, the supplied conjecture asks whether \[ \lim_{n\to\infty}\Pr\!\left(E(G_n)\ne\varnothing\ \text{and}\ \tau(G_n)=n-\beta(G_n)+1\right)=1. \] This expresses the requested equality with high probability while avoiding an undefined maximum on edgeless graphs. Any extension of $\beta$ to edgeless graphs gives the same limiting question, since their probability tends to zero.

The supplied record does not explicitly specify whether complete bipartite graphs with an empty part are permitted. The formulation above uses two nonempty parts; if the intended definition of $\beta$ includes independent sets as complete bipartite graphs with an empty part, that alternative convention must be resolved before treating this draft as definitive. The record describes this as a revised conjecture but supplies no earlier formulation or explanation of the revision.

Short English statement

For a random graph in which each possible edge appears independently with probability $1/2$, is the minimum number of bicliques whose edge sets partition all edges equal, with probability tending to one, to the number of vertices minus the largest induced biclique's order plus one? The convention concerning empty bipartition parts requires review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002468$, title Biclique Partition Numbers of Random Graphs, in the Oberwolfach Reports Open Problems collection; exact source problem code: catalogue entry. The record gives proposed year 2014 and supplies no proposer attribution.
• Supplied report citation and literature source labelled "Original OWR record": Combinatorics (2014), Oberwolfach Reports, pp. 5--90, DOI 10.4171/owr/2014/01. https://doi.org/10.4171/owr/2014/01. The supplied citation gives the report's page range, without a precise location for this problem.
• Supplied literature source labelled "Alon bipartite decomposition paper": https://www.tau.ac.il/~nogaa/PDFS/bipdec2.pdf. No fuller bibliographic details are supplied.
• Literature assessment checked on 2026-08-21: the supplied curation labels the problem open and says that the revised random-graph conjecture remains a conjecture, with available primary work presenting it as plausible without proving or disproving it. This is supplied dated curation and literature triage, not an independently verified assessment. The record expressly calls for independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified; its accompanying verification note reports manual semantic, typographic, and LaTeX review of a meaning-preserving cleanup. These are supplied record annotations, not an independent mathematical review of this draft.