Uniform asymptotics for the Kleitman-West problem
Abstract
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 Mr(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 Fj(p)=max{p1+1/j, 2p−1+(1−p)1+1/j} for 0≤ p≤1, and Gj(x)=⌊ x⌋+Fj(x−⌊ x⌋) for x≥0. With Pr(n,m)=∑j=1r(nj+1)/(2(j−1)!)Gj (j!m/nj)−(r(r−1))/4mn−m/2, we prove that limn→∞max2≤ m≤binom nr|Mr(n,m)/Pr(n,m)−1|=0. The remaining cases satisfy Mr(n,0)=Mr(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.
Related
- Extremal Families for the Erdős--Kleitman Problem: The Missing Constructions
- Exact Endpoint Asymptotics and Almost-Sure Limits for Uniform Empirical Measures in Two Dimensions
- Selberg sieve weights and sign changes of Kloosterman sums. I. Uniform asymptotics for shifted weights
- Uniform Local Asymptotics for Lévy Processes with Subexponential Jumps
- Uniform asymptotics and the Weil--Petersson constant
BibTeX
@misc{zeng2026uniform,
title = {{Uniform asymptotics for the Kleitman-West problem}},
author = {Jiasheng Zeng},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05162},
eprint = {2611.05162},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05162},
}
RIS
TY - UNPB
TI - Uniform asymptotics for the Kleitman-West problem
AU - Jiasheng Zeng
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05162
UR - https://arxiv.org/abs/2611.05162
AB - 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_r(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_j(p)=max{p^1+1/j, 2p−1+(1−p)^1+1/j} for 0≤ p≤1, and G_j(x)=⌊ x⌋+F_j(x−⌊ x⌋) for x≥0. With P_r(n,m)=∑_j=1^r(n^j+1)/(2(j−1)!)G_j (j!m/n^j)−(r(r−1))/4mn−m/2, we prove that lim_n→∞max_2≤ m≤binom nr|M_r(n,m)/P_r(n,m)−1|=0. The remaining cases satisfy M_r(n,0)=M_r(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.
ER -