= Solution
Order the <edges> arbitrarily and fix their colours one at a time. After a partial assignment $P$, regard all unassigned <edges> as independent fair red/blue choices, and compute
$$
Q(P)=\mathbb E[Z\mid P].
$$
The <conditional expectation of a monochromatic clique count> is easy to compute. For each four-<vertex> <subset> $A$, let $r$ be the number of its six <edges> still unassigned. Its contribution $q_A(P)$ to $Q(P)$ is
$$
q_A(P)=\begin{cases}
0,&\text{both colours already occur among its fixed edges},\\
2^{-r},&\text{at least one edge is fixed, all in the same colour},\\
2^{1-r}=1/32,&\text{none of its six edges is fixed}.
\end{cases}
$$
In the second case, every remaining <edge> must match the already fixed colour; this includes a completely fixed <monochromatic> copy, for which $r=0$ and the contribution is one. In the last case, the six unassigned <edges> may become either all red or all blue. By <linearity of expectation>,
$$
Q(P)=\sum_{|A|=4}q_A(P).
$$
For the next unassigned <edge> $e$, compute $Q(P,e=\text{red})$ and $Q(P,e=\text{blue})$. The <law of total expectation> gives
$$
Q(P)=\frac12Q(P,e=\text{red})+\frac12Q(P,e=\text{blue}).
$$
Choose the colour with the smaller value, resolving a tie by a fixed rule. At least one is at most their average, so the <loop invariant> is that $Q$ never increases. Initially $Q=\binom n4/32$; once every <edge> is fixed, there is no randomness left and $Q=Z$. Therefore the <method of conditional expectations> guarantees
$$
\boxed{Z\leq\frac1{32}\binom n4.}
$$
A direct implementation recomputes both sums over all $O(n^4)$ four-<vertex> <subsets> for each of the $O(n^2)$ <edges>, requiring $O(n^6)$ arithmetic operations. The comparisons can be exact: every contribution is a multiple of $1/32$, so store $32Q$ as an <integer> with $O(\log n)$ <bits>. This gives $O(n^6\log n)$ <bit complexity> with elementary arithmetic, and hence a deterministic <polynomial time> construction. No random sampling is performed by this <derandomization>.
Back to article page
