1
$\begingroup$

I am interested in the maximal number of $k$-subsets of an $n$-set such that any two subsets meet in at most $(k-2)$ points. I found that for $k=3$ and $k=4$, we have the sequences http://oeis.org/A001839 and http://oeis.org/A001843 as solutions which gives the impression that higher orders should be obtainable via $A(n,4,k)$ but this seems to be complicated when I look at the research invested in $A$.

"A binary constant weight code of word length $n$ and weight $w$ and minimum distance $d$ is a collection of $(0,1)$-vectors of length $n$, all having $w$ ones and $n - w$ zeros, such that any two of these vectors differ in at least $d$ places. The maximum size of such a code is denoted by $A(n; d;w)$." The definition of $A$ can be found here https://www.win.tue.nl/~aeb/preprints/cw4p.pdf.

I tried to say something about cases $k>5$ using the Erdös-Ko-Rado Theorem but I was not really succesfull. Is my intuition right, that $A(n,4,k)$ described exactly the quantity, which I am looking for?

$\endgroup$

1 Answer 1

2
$\begingroup$

You are looking for constant weight codes with maximum size given by $A(n,4,k).$ Yes this is a very hard problem in terms of constructions in general.

There is the following paper available online here which has some results:

Some new distance-4 constant weight codes A. E. Brouwer & T. Etzion 2010-02-18

Abstract

Improved binary constant weight codes with minimum distance 4 and length at most 28 are constructed. A table with bounds on the chromatic number of small Johnson graphs is given.

The paper has been published see here and also cited 10 times according to that link. I suggest you check out those links to see if improved bounds or constructions are available.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.