MathLabs

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

Step 5 of 7: Combine the construction with Frankl–Wilson: at least (1.2)d(1.2)^{\sqrt{d}} pieces required
In plain words

Now plug the cuts from Step 4 straight into the Frankl–Wilson theorem from Step 3: a 'piece of strictly smaller diameter' in Borsuk's sense is exactly a sub-family of cuts that avoids the one dangerous intersection size, ∣A∩C∣=k|A \cap C| = k, and the theorem says any such sub-family must be tiny compared to the whole collection. Dividing the (huge) total number of cuts by the (much smaller) largest safe sub-family gives a lower bound on how many pieces are needed — and that ratio turns out to grow like (1.2)d(1.2)^{\sqrt d}, wildly outpacing the conjectured d+1d+1.

f(d) ≥ 12(m2k)2(m−1k−1) > (1.2)d,d=(m2)−1f(d) \ \ge\ \frac{\tfrac12\binom{m}{2k}}{2\binom{m-1}{k-1}} \ >\ (1.2)^{\sqrt d}, \qquad d = \binom m2 - 1
Detailed analysis

A piece of K\mathcal K has strictly smaller diameter exactly when it contains no two cuts S(A,B),S(C,D)S(A,B), S(C,D) with ∣A∩C∣=k|A \cap C| = k (the minimal-intersection, maximal-distance pairs from Step 4). Applying the Frankl–Wilson theorem of Step 3, with the ground set VV of size n:=mn := m and forbidden intersection size n/4=kn/4 = k, any such 'safe' sub-family of K\mathcal K has size at most 2(m−1k−1)2\binom{m-1}{k-1}. Since K\mathcal K itself has 12(m2k)\tfrac12\binom{m}{2k} elements, partitioning K\mathcal K into pieces of smaller diameter requires at least 12(m2k)/2(m−1k−1)\tfrac12\binom{m}{2k} \big/ 2\binom{m-1}{k-1} pieces.

A Stirling-approximation computation (carried out for m=4km=4k with kk ranging over prime powers, using the prime number theorem to guarantee prime powers are not too sparse) shows this ratio exceeds (1.203)d(1.203)^{\sqrt d} once d=(m2)−1d = \binom{m}{2}-1 is large enough, which is exponentially larger than the conjectured d+1d+1. Since K⊂{0,1}d\mathcal K \subset \{0,1\}^d is a genuine bounded subset of Rd\mathbb{R}^d of diameter equal to the maximal distance computed in Step 4, this directly disproves Borsuk's conjecture for all sufficiently large dd.

Knowledge used in this step