---

Claim. The statement of Problem 807 is false: for $G=G(n,1/2)$ the equality $\tau(G)=n-\alpha(G)$ does not hold with probability tending to $1$. Let $\beta(G)$ be the largest number of vertices of an induced complete bipartite subgraph of $G$, and let $k_0=k_0(n)$ be the largest $k$ for which the expected number $f(k)=\binom nk2^{-\binom k2}$ of independent $k$-sets is at least $1$. Every graph satisfies $\tau(G)\le n-\beta(G)+1$, since the edges outside a largest induced complete bipartite subgraph $H$ can be covered by stars centered at the vertices outside $H$, and $H$ is one more piece. Theorem 1.1 of N. Alon, Bipartite decomposition of random graphs, J. Combin. Theory Ser. B 113 (2015), 220--235, first posted as arXiv:1402.6466 on 2014-02-26, states: (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)$, then whp one of the four combinations of $\alpha(G)\in\{k_0-1,k_0\}$ with $\beta(G)\in\{k_0+1,k_0+2\}$ holds, each with probability bounded away from $0$ and $1$; (iii) the same with $k_0+1$ in place of $k_0$ when $f(k_0+1)=\Theta(1)$. The corpus states the theorem on its result page.

The hypothesis of (i) holds for most $n$, in the sense that a uniform random integer in $[1,M]$ satisfies it with probability tending to $1$ as $M\to\infty$ (the paper, p. 3). Along those $n$ the probability of the equality tends to $0$, so it cannot tend to $1$ along all $n$, and the statement, which asks for exactly that, is false. The problem page adds a remark on the exceptional $n$: in three of the four cases of (ii) the bound $\tau(G)\le n-\beta(G)+1$ already gives $\tau(G)<n-\alpha(G)$, so the equality fails with probability bounded away from $0$ for every large $n$; that remark is the problem page's and is not part of the claim. The paper leaves open whether for the exceptional $n$ the equality holds with probability bounded away from $0$, and conjectures (Conjecture 4.1) that $\tau(G)=n-\beta(G)+1$ whp.

Depends on. Theorem 1.1 of the paper, the library's result page; the result is otherwise self-contained.

Acceptance. refereed: the Journal of Combinatorial Theory, Series B is a refereed journal, and the Crossref record of the DOI gives volume 113 (July 2015), pages 220--235, and no finer publication date. reviewed: the curator of erdosproblems.com, T. F. Bloom, labels the problem DISPROVED and credits this paper with showing the statement false, with $\tau(G)\le n-\alpha(G)-1$ almost surely (the site's page as of 2026-09-18, with an empty thread and an empty proof-claim tab); the site's label is the discussion link. The community database lists the problem disproved as of its entry's last update of 31 August 2025, which does not date any change of state. The arXiv version, the only one, is cited, on its source card; Theorem 1.1 and the definitions are checked statements (p. 2), the proof (Section 2, pp. 3--9) is not checked, and the journal text is not held. The strengthening by Alon, Bohman and Huang disproves the statement a second time, for every $n$ with high probability.