= Conditional expectation of a monochromatic clique count
In a partially fixed two-colour <edge coloring> of a <complete graph>, complete all unassigned <edges> independently and fairly. For a fixed <clique> with $r$ unassigned <edges>, its <conditional probability> of becoming <monochromatic> is zero if both colours already occur; $2^{-r}$ if a colour is fixed and no conflicting colour occurs; and $2^{1-r}$ if none is fixed. Sum these <conditional probabilities> over the <cliques> to obtain a computable <conditional expectation>. Fix each next <edge> to a colour that does not increase this <conditional expectation>, yielding a deterministic minimization construction.
Back to article page
