in the middle of some proof I encountered a combinatorial problem and tracked it back to the theory of Constant Weight Codes. Those problems seem hard to solve, but my question is rather specific, so I am still posting it in the hope for ideas:

Assume you have a set $X$ of $N$ elements (all numbers are finite). What is the largest number $k=k(N)$ such that there exist subsets $Y_1, \dots, Y_k\subseteq X$ with

  1. $|Y_i|=3$ for all $i=1,\dots, k$
  2. $|Y_i\cap Y_j|\leq 1$ for all $i\neq j$.

Ultimately I am not even interested in the explicit number, but rather in an answer to the following

Question: Does there exist some natural number $N$, such that $k(N)\geq 2N$?

In the language of Constant Weight Codes, the number $k(N)$ seems to refer to the maximal number $A(N,4,3)$ of Codewords in a binary Constant Weight Code with length $N$, Hamming distance $4$ and constant weight $3$.

I would be very thankful for suggestions.

Cheers, Sofie


I'll just adress you question as to whether there is $N$ so that $k(N)\geq 2n$. Yes, it is very possible. In fact if $N$ is $1$ or $3\bmod 6$ we can always find $\frac{n(n-1)}{6}$ subsets with this property by taking a steiner triple system.

In particular a Steiner triple system of size $13$ would have $\frac{13\cdot12}{6}=26$ subsets of size $3$. So indeed it is possible for $k(N)$ to be greater than $2n$, or $sn$ for any integer $s$ for that matter.

  • 1
    $\begingroup$ Thank you a lot for your answer. That solves my question, although I would have preferred the answer to be negative. But what can you do about truth.... $\endgroup$ – sofie Jul 15 '15 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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