1 problem

Let $G\sim G(n,(1+\varepsilon)/n)$ for a fixed $\varepsilon>0$, and let $\mathrm{Dist}_{\mathrm{BP}}(G)=|E(G)|-\mathrm{MAXCUT}(G)$ denote the distance of $G$ from bipartiteness. Co…