Semidefinite programming bounds for few-distance sets in the Hamming and Johnson spaces

2022/06/27 by Alexander Barg, Barg, Alexander, Ching–Yi Lai +5
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Packing Problems #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.2206.13617

openalex publication_date 2022/06/27 · openalex created_date 2022/07/01 · openalex updated_date 2026/07/28

Abstract

We study the maximum cardinality problem of a set of few distances in the Hamming and Johnson spaces. We formulate semidefinite programs for this problem and extend the 2011 works by Barg-Musin and Musin-Nozaki. As our main result, we find new parameters for which the maximum size of two- and three-distance sets is known exactly.

Related

• New upper bound for the cardinalities of s-distance sets on the unit sphere
• Constructions of maximum few-distance sets in Euclidean spaces
• New bounds for spherical two-distance sets
• On subsets of the hypercube with prescribed Hamming distances
• K-distance sets, Falconer conjecture, and discrete analogs