A(k,4,r) is the independence number of the Johnson graph J(k,r). What is the best known asymptotic lower bound on A(k,4,floor(k/2)) ? I only obtained $\frac{{k\choose\lfloor{k/2}\rfloor}}{\lfloor{k^2/4}\rfloor}$.

## 1 Answer

A better bound than that is known. Define a function $f:\{0,1\}^n\to \{0,1,\dots,n-1\}$ as follows: $$ f(c_0,c_1,\dots,c_{n-1})=\left(\sum_{i=0}^{n-1} i\cdot c_i\right)\bmod n.$$ Then define the following codes, $$ C_a=\{ c=(c_0,c_1,\dots,c_{n-1})\in\{0,1\}^n ~|~ wt(c)=w, f(c_0,c_1,\dots,c_{n-1})=a \},$$ where $wt(c)$ denotes the Hamming weight of $c$.

It is a simple exercise to see that each $C_a$ is a constant-weight code with minimum Hamming distance 4, i.e., an independent set in $J(n,w)$. Since the $n$ codes form a partition of the vertices of $J(n,w)$, there is one of size at least $\frac{1}{n}\binom{n}{w}$.

In your case this translates to $A(k,4,\lfloor k/2\rfloor)\geq \frac{\binom{k}{\lfloor k/2\rfloor}}{k}$.

This taken from: R. L. Graham and N. J. A. Sloane, "Lower bounds for constant weight codes," IEEE Transactions on Information Theory, vol. IT-26, pp. 37-43, 1980.