2022/12/16 by Benjamin Gunby, Xiaoyu He, Gunby, Benjamin +5
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2212.08406
openalex publication_date 2022/12/16 · openalex created_date 2023/01/03 · openalex updated_date 2026/07/28
A family of sets A is said to be an antichain if x\not⊂ y for all distinct x,y∈ A, and it is said to be a distance-r code if every pair of distinct elements of A has Hamming distance at least r. Here, we prove that if A⊂ 2[n] is both an antichain and a distance-(2r+1) code, then |A| = Or(2n n-r-1/2). This result, which is best-possible up to the implied constant, is a purely combinatorial strengthening of a number of results in Littlewood--Offord theory; for example, our result gives a short combinatorial proof of Hálasz's theorem, while all previously known proofs of this result are Fourier-analytic.