Problem 807

The bipartition number $\tau(G)$ of a graph $G$ is the smallest number of pairwise edge disjoint complete bipartite graphs whose union is $G$ . The independence number $\alpha(G)$ is the size of the largest independent subset of $G$ .

Is it true that, if $G$ is a random graph on $n$ vertices with edge probability $1/2$ , then

\tau(G)=n-\alpha(G)

almost surely?

Source: erdosproblems.com/807

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved; the site labels the problem DISPROVED. Theorem 1.1 of [Al15] (J. Combin. Theory Ser. B 113 (2015), 220--235; refereed; cited from the arXiv version): with $k_0$ the largest $k$ such that the expected number $f(k)=\binom nk2^{-\binom k2}$ of independent $k$ -sets in $G(n,1/2)$ is at least $1$ , and $\beta(G)$ the largest number of vertices of an induced complete bipartite subgraph, (i) if $1=o(f(k_0))$ and $f(k_0+1)=o(1)$ then whp $\alpha(G)=k_0$ and $\beta(G)=k_0+2$ , so $\tau(G)\le n-\alpha(G)-1$ whp; (ii) if $f(k_0)=\Theta(1)$ , whp one of the four combinations of $\alpha(G)\in\{k_0-1,k_0\}$ and $\beta(G)\in\{k_0+1,k_0+2\}$ holds, each with probability bounded away from $0$ and $1$ ; (iii) if $f(k_0+1)=\Theta(1)$ , the same with $k_0+1$ in place of $k_0$ . In each of (ii) and (iii) three of the four combinations give $\tau(G)<n-\alpha(G)$ through $\tau(G)\le n-\beta(G)+1$ . So the equality fails with high probability for most $n$ and with probability bounded away from zero for every large $n$ , and the statement is false. Theorem 1.1 of [ABH17] (J. Graph Theory 84 (2017), 45--52; refereed; cited from the arXiv version) strengthens this to $\tau(G)\le n-(2+2c)\log_2n\le n-(1+c)\alpha(G)$ whp for an absolute constant $c>0$ , for every $n$ . The typical value of $\tau(G(n,1/2))$ remains open between Chung and Peng's $n-o((\log n)^{3+\varepsilon})$ (second-hand) and this bound. Both results and their acceptance evidence are recorded on the claim pages Alon's Theorem 1.1 and Alon, Bohman and Huang's Theorem 1.1, from which the frontmatter is derived.

Al15: Alon, N., Bipartite decomposition of random graphs. J. Combin. Theory Ser. B 113 (2015), 220--235, doi:10.1016/j.jctb.2015.03.001 (as its Crossref record gives it); arXiv:1402.6466v1 (26 February 2014; the only arXiv version). Theorem 1.1, the definitions of $\beta(G)$ and $k_0$ and the bound $\tau(G)\le n-\beta(G)+1$ , p. 2; the sense of "most $n$ ", p. 3; Conjecture 4.1 and the closing remarks, p. 13. Library home: Alon 2015; paged at Alon 2015, Theorem 1.1.
ABH17: Alon, N., Bohman, T. and Huang, H., More on the bipartite decomposition of random graphs. J. Graph Theory 84 (2017), no. 1, 45--52, doi:10.1002/jgt.22010 (online 22 February 2016, as its Crossref record gives it); arXiv:1409.6165v1 (22 September 2014; the only arXiv version). Theorem 1.1 and inequality (1), p. 2; the concluding remarks, p. 6. Library home: Alon and Huang 2017; paged at Alon and Huang 2017, Theorem 1.1.
KRW88: Kratzke, T., Reznick, B. and West, D., Eigensharp graphs: decomposition into complete bipartite subgraphs. Trans. Amer. Math. Soc. 308 (1988), no. 2, 637--653, doi:10.1090/S0002-9947-1988-0929670-5 (received 26 January 1987, as its Crossref record gives it; the site's reference text gives "(1988), 637--653" with no volume). The definition of $\tau(G)$ , p. 637; the star bound and Erdős's conjecture, p. 638. Library home: Kratzke and West 1988 (the AMS back file); paged at Kratzke and West 1988, Conjecture (p. 638).
ChPe: Chung, F. and Peng, X., Decomposition of random graphs into complete bipartite graphs. arXiv:1402.0860 (cited so by [Al15] and [ABH17]; a citation index lists a version in SIAM J. Discrete Math.). Not held; its bounds are quoted from p. 1 of [Al15] and p. 1 of [ABH17].
BoHo22: Bohman, T. and Hofstad, J., A critical probability for biclique partition of $G_{n,p}$ . arXiv:2206.13490 (v4 8 January 2024); published as J. Combin. Theory Ser. B 166 (2024), 50--79, doi:10.1016/j.jctb.2023.12.005. A lead on the variant with $p<1/2$ , recorded below. - Graham and Pollak's theorem $\tau(K_n)=n-1$ ([Al15], p. 1; [KRW88], p. 638) is context; their paper is not held.

Problem 807

Status

Proof claims

Discussion