4
$\begingroup$

Does it have name or is it even researched. I was trying to calculate some combinatorial problems and ran into a problem. I do not know how to calculate (in general) the maximal number of k-element subsets, such that any pair of these subsets differs in at least two elements.

For example, $3$-element subsets of $\{1,2,3,4,5\}$ with the above property are only $2$, for instance $\{1,2,3\}$ and $\{1,4,5\}$. I know it is going to be most likely complicated, because by my calculations 3-element subsets with this property for $n = 1 \text{ or } 3\mod 6$ turned out to be equal to $\frac {n \choose 2} 3$. And I know why (in case I am not wrong), and I guess it is due to its connection to that type of algebra I do not know the name of, where given two different elements, the result of the operation is the third one (please tell me how is it called).

But this equality does not apply for other numbers in case of $3$-element subsets, because not every pair of elements determines some triplet. And more complication I guess arises in general case of k-element subsets.

Is it something known and solvable, something known and not having a general way of computing it, or is it a not researched topic?

$\endgroup$
  • $\begingroup$ Consider the $k$-element subsets of an $m$-set as the vertices of a graph, with edges corresponding to pairs of subsets differing by a single element. Then you're asking for the independence number of this graph. $\endgroup$ – Robert Israel Oct 11 '17 at 8:16
  • $\begingroup$ @RobertIsrael Thanks, I thought of that, but that is a NP-hard problem in general case, graphs corresponding to subsets with edges between those differing in one element are not general graphs. That might be special case with faster solution. $\endgroup$ – TStancek Oct 11 '17 at 8:28
1
$\begingroup$

For $k$-element subsets, this is in general known as the coding-theoretic function $A(n, 4, k)$: the number of codewords in $\{0,1\}^n$ with constant weight $k$ and minimum distance $4$.

For $k=3$, you can find this sequence in the OEIS under A001839 where the following closed formula is given: $$A(n,4,3) = \begin{cases}\left\lfloor \frac n3 \left\lfloor \frac{n-1}{2}\right\rfloor\right\rfloor - 1 & n \equiv 5 \pmod 6 \\ \left\lfloor \frac n3 \left\lfloor \frac{n-1}{2}\right\rfloor\right\rfloor & n \not\equiv 5 \pmod 6 \end{cases}$$ See this index for several other sequences $A(n,d,w)$ in the OEIS.

The paper New table of constant weight codes has a table of $A(n,4,w)$ for various values of $w$. In particular, we also know that $$A(n,4,4) = \begin{cases} \frac{n(n-1)(n-2)}{24} & n \equiv 2,4 \pmod 6 \\ \frac{n(n-1)(n-3)}{24} & n \equiv 1,3 \pmod 6 \\ \frac{n(n^2-3n-6)}{24} & n \equiv 0 \pmod 6 \end{cases}$$ with the exact value being unknown for $n \equiv 5 \pmod 6$.

It's possible that there are more up-to-date sources, this is just the paper cited in the OEIS entry.

$\endgroup$
  • $\begingroup$ I'll look into it. Thanks. $\endgroup$ – TStancek Oct 17 '17 at 14:23

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.