Worked solution: Kahn–Kalai's disproof of Borsuk's conjecture via the Frankl–Wilson theorem
Take labelled dots and draw every possible edge between them (a complete graph); each way of splitting the dots into two equal halves defines a 'cut' — the collection of edges that cross between the two halves. Kahn and Kalai treat each cut as a -vector indexed by all the edges, living in a space whose dimension is the total number of edges, and use exactly the family of all such cuts as their test case for Borsuk's conjecture.
Let with for a prime power, and let be the set of all unordered pairs of elements of — the edges of the complete graph on — so is the ambient dimension. For every partition of into two halves of size each, let be the set of pairs with one element in and one in (the 'cut' between and ); note for every such partition. Let a balanced partition of , a family of subsets of , each identified with a -vector in .
Because every set in has exactly the same size , all points of lie on a common sphere in centred at the all- point, and by Step 2's distance formula their pairwise distances are governed entirely by : two cuts are close together exactly when their crossing-edge sets overlap a lot. The smallest overlap — and hence the largest distance, the one realising 's diameter — turns out (by direct computation with the inclusion–exclusion of ) to occur exactly when , setting up the intersection condition that Step 3's theorem is built to control.
- cut of a graph
- Given a partition of a graph's vertices into two parts , the cut is the set of edges with one endpoint in and the other in ; the size of a cut counts how many edges 'cross' between the two sides.