8
$\begingroup$

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

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

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.