2024/01/01 by Miao Liu, Liu, Miao, Chong Shangguan +1 · 1 citation
Computer Science · Engineering · Biochemistry, Genetics and Molecular Biology · #Coding theory and cryptography #graph theory and CDMA systems #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.2401.00733
Constant weight codes (CWCs) and constant composition codes (CCCs) are two important classes of codes that have been studied extensively in both combinatorics and coding theory for nearly sixty years. In this paper we show that for \it all fixed odd distances, there exist near-optimal CWCs and CCCs asymptotically achieving the classic Johnson-type upper bounds. Let Aq(n,w,d) denote the maximum size of q-ary CWCs of length n with constant weight w and minimum distance d. One of our main results shows that for \it all fixed q,w and odd d, one has limn→∞\fracAq(n,d,w)\binomnt=\frac(q-1)t\binomwt, where t=(2w-d+1)/(2). This implies the existence of near-optimal generalized Steiner systems originally introduced by Etzion, and can be viewed as a counterpart of a celebrated result of Rödl on the existence of near-optimal Steiner systems. Note that prior to our work, very little is known about Aq(n,w,d) for q≥ 3. A similar result is proved for the maximum size of CCCs. We provide different proofs for our two main results, based on two strengthenings of the well-known Frankl-Rödl-Pippenger theorem on the existence of near-optimal matchings in hypergraphs: the first proof follows by Kahn's linear programming variation of the above theorem, and the second follows by the recent independent work of Delcour-Postle, and Glock-Joos-Kim-Kühn-Lichev on the existence of near-optimal matchings avoiding certain forbidden configurations. We also present several intriguing open questions for future research.