|
Near-optimal constructions of constant weight codes and constant composition codes asymptotically attaining the Johnson bound: the odd distances
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 $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$, one has
$\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, and can 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. We also present several intriguing open questions for future research.
|