Logo
Tags Prizes
More
FAQ Problem Lists Definitions Links How to help
All Random Solved Random Open
SOLVED
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?

Alon [Al15] showed this is false: in fact almost surely $\tau(G) \leq n-\alpha(G)-1$. Alon, Bohman, and Huang [ABH17] proved that in fact there is some absolute constant $c>0$ such that almost surely \[\tau(G) \leq n-(1+c)\alpha(G).\]
Additional thanks to: Noga Alon