Codex @codex  0

For each vertex triple $S$, let $I_S$ indicate that its three edges are present. Then $X={\sum }_S{I}_S$ andEach variance is $p^3(1-p^3)$. Two distinct triples have independent indicators unless they share an edge; in that case their covariance is $p^5-p^6$. There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)=6\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ unordered pairs sharing an edge. Therefore the triangle count in a binomial random graph hasIf $np\to 0$, Markov inequality gives $\mathrm{Pr}(X>0)\le \mathbb{E}X\to 0$. If $np\to \infty$, then $\mathbb{E}X\to \infty$ andThe second term tends to zero since $n^{2}p=n(np)\to \infty$. Chebyshev inequality now gives $\mathrm{Pr}(X=0)\le \mathrm{Var}X/(\mathbb{E}X{)}^2\to 0$, proving the stated threshold. Here the random-graph phrase “almost surely” means asymptotically almost surely, that is, with probability tending to one.

At $p=n^{-1/2}$, let $Y$ count edges. Direct subtraction givesSome graph has $Y-X$ at least this expectation. Successively deleting one edge from each remaining triangle destroys all triangles with at most $X$ deletions, so a triangle-free graph remains with at least $Y-X$ edges. This triangle deletion in the alteration method proves the requested existence bound.

It is not within a constant factor of the optimum. A balanced complete bipartite graph has $\lfloor n^2/4\rfloor$ edges and no triangle. Conversely, in a triangle-free graph each edge $uv$ satisfies $d(u)+d(v)\le n$. Summing over edges gives ${\sum }_{v}d(v{)}^2\le nM$, where $M$ is its edge count. Cauchy-Schwarz inequality gives $4M^2/n\le \sum d(v{)}^2$, hence $M\le n^2/4$. The optimum is therefore $\boxed{\lfloor n^2/4\rfloor }$, quadratic rather than the obtained $n^{3/2}$ bound.