Finite-torus crossing amplification 2026-10-14
Take the increasing event that a finite square torus graph contains some long horizontal or vertical rectangle crossing. Translations and a quarter turn make this a transitive increasing event on its bonds. A positive critical crossing bound and the Friedgut-Kalai sharp threshold theorem make its supercritical probability tend to one. A bounded family of shorter, thicker rectangles intercepts every possible long crossing. The square-root trick for positively associated events transfers the high probability to each fixed intercepting rectangle. Using every possible translate would lose the useful bounded exponent.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 13 6 ii Solution Created 2026-10-03 Updated 2026-10-14
Let be the torus graph , with independent bond density . For large, all rectangles below are too small to identify any of their own vertices or edges. Let be the event that somewhere in there is a horizontal open crossing of a by rectangle or a vertical open crossing of an by rectangle. It is increasing and invariant under translations and a quarter turn. These symmetries act transitively on all bonds, including both orientations. Thus it is a transitive increasing event.
A fixed by rectangle has its ordinary planar distribution, so the supplied lower bound gives . Choose any . Since is fixed and , the Friedgut-Kalai sharp threshold theorem implies for all sufficiently large . As is arbitrary,It remains to transfer this symmetric statement to a fixed rectangle, without a growing union-bound loss. On each circular coordinate take the ten positions , . Consecutive circular gaps are at most . Use the one hundred by rectangles starting at pairs and their one hundred quarter-turn images. Every crossed by rectangle contains the full horizontal width of one of the first family, with its vertical span contained in that rectangle's height- span: the permissible starting intervals in each coordinate have length , so the chosen positions always supply a suitable start. The crossing, restricted between those two vertical sides, gives a crossing of the chosen by rectangle. The analogous assertion holds in the rotated family.
Consequently implies at least one of these two hundred increasing crossing events. Their common success probability is . The nth root trick givesOnly two hundred translates are used, independently of scale. This bounded exponent is the essential finite-torus crossing amplification step.
For a requested height , set . Glue width-, height- rectangles, each successive pair overlapping in a square of side . Their horizontal crossings and the vertical overlap crossings imply a crossing of the union, which has width . An overlap square has crossing probability at least . Thus the Harris lemma givesChoose fixed and large enough that for all sufficiently large . Increasing height and shortening width can only help, so uniformly for ,In particular it exceeds for every sufficiently large , with the bound depending only on .