MO1.R7.4

Near-optimal constructions of constant weight codes and constant composition codes asymptotically attaining the Johnson bound

Miao Liu, Chong Shangguan, Shandong University, China

Session:
Combinatorial Coding Theory 1

Track:
1: Algebraic Aspects of Coding Theory

Location:
VIP

Presentation Time:
Mon, 8 Jul, 11:05 - 11:25

Session Chair:
Ago-Erik Riet,
Abstract
"THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD." Constant weight codes (CWCs) and constant composition codes (CCCs) are two important classes of codes that have been extensively studied in the fields of combinatorics and coding theory for nearly 60 years. In this paper, we demonstrate that for {\it all} fixed odd distance, there are near-optimal CWCs and CCCs asymptotically achieving the classic Johnson-type upper bounds. Let $A_q(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$, we have $\lim_{n\rightarrow\infty}\frac{A_q(n,d,w)}{\binom{n}{t}}=\frac{(q-1)^t}{\binom{w}{t}}$, where $t=\frac{2w-d+1}{2}$. This implies the existence of near-optimal generalized Steiner systems originally introduced by Etzion. It can also be viewed as a counterpart of a celebrated result of R\"odl on the existence of near-optimal Steiner systems. Note that prior to our work, very little is known about $A_q(n,w,d)$ for $q\ge 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\"odl-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\"uhn-Lichev on the existence of near-optimal matchings avoiding certain forbidden configurations. A full version of this paper is available at https://arxiv.org/abs/2401.00733
Resources