# lower bound on A(k,4,floor(k/2))

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}$.

• Did you compare this with known upper bounds (e.g. Delsarte bound)? Commented Apr 28, 2015 at 11:35

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}$.