MathLabs

Worked solution: Kahn–Kalai's disproof of Borsuk's conjecture via the Frankl–Wilson theorem

Step 4 of 7: Kahn and Kalai's construction: cuts of a complete graph as points in Rd\mathbb{R}^d
In plain words

Take mm 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 (0,1)(0,1)-vector indexed by all the edges, living in a space whose dimension dd is the total number of edges, and use exactly the family of all such cuts as their test case for Borsuk's conjecture.

V={1,…,m}, m=4k;W={pairs of V};K={S(A,B):{A,B} partitions V, ∣A∣=2k}V=\{1,\ldots,m\},\ m=4k;\quad W = \{\text{pairs of } V\};\quad \mathcal K = \{S(A,B) : \{A,B\} \text{ partitions } V,\ |A|=2k\}
Detailed analysis

Let V={1,…,m}V = \{1, \ldots, m\} with m=4km = 4k for kk a prime power, and let WW be the set of all (m2)\binom{m}{2} unordered pairs of elements of VV — the edges of the complete graph on VV — so d:=∣W∣=(m2)d := |W| = \binom{m}{2} is the ambient dimension. For every partition {A,B}\{A,B\} of VV into two halves of size 2k2k each, let S(A,B)⊂WS(A,B) \subset W be the set of pairs with one element in AA and one in BB (the 'cut' between AA and BB); note ∣S(A,B)∣=(2k)2=m2/4|S(A,B)| = (2k)^2 = m^2/4 for every such partition. Let K={S(A,B):{A,B}\mathcal K = \{S(A,B) : \{A,B\} a balanced partition of V}V\}, a family of (m2k)/2\binom{m}{2k}/2 subsets of WW, each identified with a (0,1)(0,1)-vector in Rd\mathbb{R}^d.

Because every set in K\mathcal K has exactly the same size m2/4m^2/4, all points of K\mathcal K lie on a common sphere in Rd\mathbb{R}^d centred at the all-12\tfrac12 point, and by Step 2's distance formula their pairwise distances are governed entirely by ∣S(A,B)∩S(C,D)∣|S(A,B) \cap S(C,D)|: 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 K\mathcal K's diameter — turns out (by direct computation with the inclusion–exclusion of A,B,C,DA, B, C, D) to occur exactly when ∣A∩C∣=k|A \cap C| = k, setting up the intersection condition that Step 3's theorem is built to control.

Terms in this step
cut of a graph
Given a partition of a graph's vertices into two parts A,BA, B, the cut S(A,B)S(A,B) is the set of edges with one endpoint in AA and the other in BB; the size of a cut counts how many edges 'cross' between the two sides.
Knowledge used in this step