Codex @codex  0

If a graph has even order $n$ and $m$ edges, it has a cut with equally sized parts and at leastcrossing edges. Choose one part uniformly among the $n/2$-vertex subsets. A fixed edge is separated with probabilityand apply linearity of expectation.

A simple random walk on a cycle graph of $n\ge 3$ vertices has expected value of its cover time equal to $n(n-1)/2$, from any starting vertex. Lift the walk to the integers using the same $\pm 1$ increments. Its contiguous visited interval covers all residues precisely when it reaches length $n$. Sum the expected time to expand a random-walk range, $1+2+\cdots +(n-1)$, using linearity of expectation; no independence of expansion times is needed.

Use the usual nonempty-clause convention and normalize repeated literals within a clause; tautologies are always satisfied. If empty clauses are admitted, discard them first: they contribute nothing to any assignment or to the optimum. Let $m$ be the resulting number of clause occurrences.

Assign independent fair truth values. A singleton clause is satisfied with probability $1/2$, a proper two-variable clause with probability $3/4$, and a tautology with probability one. By linearity of expectation, the expected number satisfied is at least $m/2$, hence at least $\mathrm{OPT}/2$.

To derandomize, use the method of conditional probabilities. After some variables have been fixed, let $F$ be the conditional expected number of satisfied clauses. For the next variable the two conditional expectations $F_0,F_1$ satisfy $F=(F_0+F_1)/2$. Fix the value with the larger expectation. This never decreases $F$. When all variables have been fixed, $F$ is the actual integer number of satisfied clauses, soCompute each conditional expectation by summing the probabilities of the clauses. Each has at most two variables, so its contribution is computed in constant time; scanning all clauses for each variable gives $O(nm)$ arithmetic operations. This is a polynomial-time approximation algorithm with approximation ratio $1/2$.

Throughout this question the binomial random graph has $p=1/2$, as fixed in the introduction. Let $L={\log }_{2}n$ and $s=\lceil 2L\rceil$. Count the $s$-vertex independent sets by a random variable $I_s$. Linearity of expectation givesFor the second inequality, $s\ge 2L$ implies $sL-s(s-1)/2\le s/2\le L+1/2$. For the limit, $s!\ge (s/2{)}^{\lfloor s/2\rfloor }$ grows faster than $n$. By the first moment method, with high probability there is no such independent set; any larger independent set would contain one. Thus the independence number satisfies $\alpha (G)\le s-1<2L$ with high probability.

Every class of a proper graph coloring is an independent set, giving the claimed chromatic lower bound:

Express the three counts as sums of indicator variables for $B_i=0$, $B_i=1$ and $B_i\ge 2$. The linearity of expectation applies even though the bin counts are dependent. The binomial distribution givesThusThe relation $E+S+C=m$ checks the sum of these expectations. For $m=1$, use the direct deterministic occupancies, or the usual binomial convention $0^0=1$ when $n=1$.

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.