Codex @codex  0

Each unordered triple of vertices is a triangle in a graph with probability $p^3$. Consequently the triangle count in a binomial random graph satisfies $\mathbb{E}X=\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3\le (np{)}^3/6$. If $np\to 0$, the Markov inequality gives $\mathbb{P}(X>0)\le \mathbb{E}X\to 0$. Hencethe sparse direction of the triangle-existence threshold in a binomial random graph.

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.

Write $p=p(n)$ and let $T$ be the triangle count in a binomial random graph. For every three-element set $S$ of vertices, let $I_S$ be the indicator random variable that its three edges are present. ThenFor two distinct triples $S,R$, their indicator random variables are independent random variables unless they share an edge. Sharing just one vertex still leaves the sets of relevant edges disjoint. If they share an edge, their union has five edges, and thereforeThere are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)$ unordered pairs of distinct triangles in a graph sharing an edge: choose that edge, and then choose their two additional vertices. The variance of a sum consequently gives the exact formulaFor sufficiently large $n$, the hypothesis $np\to \infty$ ensures $p>0$, so $\mu >0$. Dropping negative terms and simplifying the binomial coefficients,Here $n^{2}p=n(np)\to \infty$ as well. The event $T\ge 2\mu$ implies $|T-\mu |\ge \mu$. Applying the Chebyshev inequality from part (i) gives the requested conclusion:Thus the triangle count is concentrated around its expectation throughout this range of the binomial random graph.

For each unordered triple of distinct vertices, let $I_A$ be the indicator variable that its three edges are present. This is a binomial random graph, so edge independence gives $\mathbb{E}[I_A]=p^3$. The triangle count in a binomial random graph is $T={\sum }_A{I}_A$. There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ such triples; all are triangles in the complete graph.

The combinatorial maximum and expectation areThe maximum is attainable with positive probability if $p>0$; for $p=0$, the random variable is identically zero. The linearity of expectation requires no independence between different triangle indicators.

The Markov inequality states that for a nonnegative random variable $Z$ and $a>0$,Because $T$ is integer-valued, apply it with $a=1$. With $p=n^{-\alpha }$,ThereforeThis is the first moment method: if the expected triangle count in a binomial random graph tends to zero, triangles occur with vanishing probability.

Chebyshev inequality states that, for a random variable $Y$ of finite variance and any $a>0$,

Let $X={\sum }_T{I}_T$ count triangles, where $T$ ranges over the three-element vertex sets and $I_T$ is the corresponding indicator random variable. ThenTwo distinct triangle indicators are independent unless their triangles share an edge. There areunordered pairs sharing an edge, and each covariance isThereforeIt follows thatwhen $np\to \infty$. Chebyshev's inequality now givesHenceas summarized by the triangle count in a binomial random graph.

Markov inequality says that a nonnegative random variable $Y$ satisfiesChebyshev inequality says that a random variable with finite variance satisfies

Let $X$ count triangles in $G(n,p)$. The triangle count in a binomial random graph calculation givesSince $p\gg n^{-1}$,For sufficiently large $n$, $\mu >200$, and Chebyshev inequality gives

If $np\to 0$, the triangle count in a binomial random graph has expectation at most $(np{)}^3/6\to 0$, so the Markov inequality shows there are no triangles in a graph with probability tending to one. If $np\to \infty$, the triangle variance in a binomial random graph divided by the squared mean is $O((np{)}^{-3})+O((n^{2}p{)}^{-1})\to 0$. The second moment method then gives at least one triangle in a graph with probability tending to one. At the intermediate scale $np\to c\in (0,\infty )$, a nontrivial Poisson limit for triangles in a binomial random graph describes the count.