Uniform asymptotics for the Kleitman-West problem

Two distinct r-element sets are adjacent if their intersection has size $r-1$. The Kleitman-West problem, equivalently formulated as the edge-isoperimetric problem on the Johnson graph $J(n,r)$, asks for the maximum number Mᵣ(n,m) of unordered adjacent pairs in a family of m r-element subsets of an n-element set, and for the families attaining this maximum. For every fixed integer r≥2, we determine this maximum asymptotically as n→∞, uniformly over the entire range of family sizes. Specifically, for each integer 1≤ j≤ r, define Fⱼ(p)=max1+1/j,\,2p-1+(1-p)1+1/j\ for 0≤ p≤1, and Gⱼ(x)= x+Fⱼ(x- x) for x≥0. With \[ P_r(n,m)=∑ⱼ₌₁^r{nʲ⁺¹}{2(j-1)!}G_j\!(j!m/n^j)-{r(r-1)}4mn- m2, \] we prove that \[ limn→∞max2≤ m≤ nr|M_r(n,m)/P_r(n,m)-1|=0. \] The remaining cases satisfy Mᵣ(n,0)=Mᵣ(n,1)=0. The proof first establishes the asymptotic formula for dense families using a sharp inequality for bounded random variables, with equality attained by a random variable taking at most two values. To extend the result uniformly to all family sizes, we extract groups of sets sharing a fixed subset, apply the dense estimates after deleting that subset, and control the adjacent pairs not contained in any one group.