The probabilistic method in combinatorics — pioneered by Erdős — shows that random constructions often achieve surprising results. Color the integers randomly, and the expected number of monochromatic patterns (arithmetic progressions, constellations) follows from straightforward counting. The question Butler, Costello, and Graham asked in 2010: can you do better than random?
Yang and Mao prove yes, for every constellation pattern. There exists a deterministic coloring of the integers 1 through n that produces fewer monochromatic copies of any given pattern than the expected count under random coloring. The improvement is multiplicative — the leading coefficient γ is strictly smaller than the random coefficient — not just a lower-order correction.
This is surprising because the probabilistic method often gives optimal or near-optimal results. For many combinatorial problems, random constructions are the best known and sometimes provably optimal. That deterministic colorings can systematically beat random for all constellations means there's exploitable structure in the pattern-avoidance problem that randomness misses.
The resolution inverts the usual relationship between structure and randomness in combinatorics. Normally, structure helps construct objects (you need careful design to build extremal graphs) while randomness helps avoid patterns (random constructions minimize unwanted substructures). Here, structure helps avoid patterns too. The constellation's geometry creates correlations that a deterministic coloring can exploit — correlations that random coloring, by definition, ignores. The randomness that usually solves avoidance problems is leaving performance on the table.