= Solution
Set $N=\binom n4$. Independently sample an <edge coloring> exactly as in part (d), count its <monochromatic> copies of $K_4$ by examining all four-<vertex> <subsets>, and accept precisely when $32Z\leq N$. Otherwise start over with a fresh <edge coloring>.
To prove an expected <polynomial time> bound, the existence argument alone is insufficient: we need a lower bound on the acceptance <probability> at this exact threshold. Since $32Z$ is a nonnegative <integer> with <expectation> $N$, rejection implies $32Z\geq N+1$. <Markov's inequality> therefore gives the <integer-valued expectation threshold restart bound>
$$
\mathbb P(\text{reject})\leq\frac{N}{N+1},
\qquad
\boxed{\mathbb P(\text{accept})\geq\frac1{N+1}.}
$$
The number of attempts has a <geometric distribution>, with <expectation> at most $N+1$. Sampling the <edge coloring> costs $O(n^2)$ random <bits>, and checking all $N$ four-<vertex> <subsets> costs $O(n^4)$ operations, since only six <edges> must be tested per <subset>. Hence
$$
\boxed{\mathbb E[\text{running time}]=O((N+1)n^4)=O(n^8).}
$$
This is a <randomized algorithm> that always returns an <edge coloring> meeting the original threshold and terminates with <probability> one. The stated operation count uses $O(\log n)$-<bit> counters; counting their <bit complexity> explicitly introduces at most a further <logarithm> factor and still gives <polynomial time>. For $n<4$, return any <edge coloring> immediately.
Back to article page
