2025/04/16 by Dong, Zichao, Gao, Jun, Liu, Hong +2
#05C35 #05D05 (primary) #52C10 #94B25 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2504.12296
Denote by fD(n) the maximum size of a set family F on [n] \stackrel\normalfont\tiny def= \1, …, n\ with distance set D. That is, |A \bigtriangleup B| ∈ D holds for every pair of distinct sets A, B ∈ F. Kleitman's celebrated discrete isodiametric inequality states that fD(n) is maximized at Hamming balls of radius d/2 when D = \1, …, d\. We study the generalization where D is a set of arithmetic progression and determine fD(n) asymptotically for all homogeneous D. In the special case when D is an interval, our result confirms a conjecture of Huang, Klurman, and Pohoata. Moreover, we demonstrate a dichotomy in the growth of fD(n), showing linear growth in n when D is a non-homogeneous arithmetic progression. Different from previous combinatorial and spectral approaches, we deduce our results by converting the restricted distance problems to restricted intersection problems. Our proof ideas can be adapted to prove upper bounds on t-distance sets in Hamming cubes (also known as binary t-codes), which has been extensively studied by algebraic combinatorialists community, improving previous bounds from polynomial methods and optimization approaches.