4
$\begingroup$

This question is motivated by a real-world application related to an art project that involves displaying images, but my search hit a dead end after finding the wikipage about Kirkman systems (other related terms include Steiner systems and the Social golfer problem) and looking over references linked there. A few people have written programs for this specific question that established lower bounds (so: more than $2100$) but none has found an exact answer.

The question is:

Given a set of $40$ elements, what is the maximum number of subsets, each with $4$ elements, that can be created such that no triple appears more than once?

(For example, if the set includes $A,B,C,D,E$ as elements, then one cannot include in the collection of subsets both $\{A,B,C,D\}$ and $\{A,B,C,E\}$ since, in this scenario, we would have the triple $A,B,C$ appearing more than once.)

As an excerpt from the History section of the aforelinked wikipage, there is under the first bullet point a question attributed to Wesley Woolhouse (1844):

"Determine the number of combinations that can be made out of $n$ symbols, $p$ symbols in each; with this limitation, that no combination of $q$ symbols, which may appear in any one of them shall be repeated in any other."

followed by the formula:

$$\frac{n!}{q!(n-q)!)} \div \frac{p!}{q!(p-q)!}$$

Unfortunately, one finds that this formula is false already for small examples (e.g. $n=5, p=4, q=3$) and, indeed, reading further on that page indicates that the formula only holds in certain scenarios.

Rephrased, I am looking for an answer to Woolhouse's question for the case of $n=40, p=4, q=3$ either by a counting argument, an effective program, or a reference. Please tag/retag as appropriate; thanks!

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ You write "Given a set of 40 elements, what is the maximum number of subsets that can be created such that no triple appears more than once?" Given the context in the rest of the question, do I gather correctly that you meant to include the additional condition that each subset has $4$ elements? $\endgroup$
    – David E Speyer
    Commented Feb 13, 2022 at 21:20
  • 3
    $\begingroup$ As a lower bound, $\{ \{ a,b,c,d \} : a+b+c+d \equiv 2 \bmod 40 \}$ has 2290 elements, and clearly has no two elements which overlap in size three; this is not too far from the ratio of binomial coefficients, which gives 2470. $\endgroup$
    – David E Speyer
    Commented Feb 13, 2022 at 21:25
  • 2
    $\begingroup$ Another way to rephrase this problem is that you are looking for the largest anticlique in the Johnson graph $J(40,4)$. Wikipedia tells me that determining the chromatic number of Johnson graphs is open, which makes me suspect the situation for anticliques will be just as bad. en.wikipedia.org/wiki/Johnson_graph $\endgroup$
    – David E Speyer
    Commented Feb 13, 2022 at 21:32
  • 2
    $\begingroup$ Using $\mathbb{Z}/5 \mathbb{Z} \times (\mathbb{Z}/2 \mathbb{Z})^3$ instead of the cyclic group of order $40$ improves the lower bound to 2318 (now achieved at the zero element). $\endgroup$
    – David E Speyer
    Commented Feb 13, 2022 at 21:45
  • 2
    $\begingroup$ By computer. I had Mathematica add up all 4-tuples of distinct elements in the abelian group I listed and count which sum was most frequent; the most frequent was the zero element of the group, which occurred 2318 times. (I hope there are no errors.) $\endgroup$
    – David E Speyer
    Commented Feb 14, 2022 at 1:27

1 Answer 1

Reset to default
9
$\begingroup$

In fact, Wikipedia article on Steiner systems that you linked already provides an answer to your question:

An $S(3,4,n)$ is called a Steiner quadruple system. A necessary and sufficient condition for the existence of an $S(3,4,n)$ is that $n \equiv 2\ \text{or}\ 4 \pmod6$.

Notice that $40\equiv 4\pmod{6}$, and so Steiner system $S(3,4,40)$ does exist. It is formed by $\frac{\tbinom{40}{3}}{\tbinom43} = 2470$ blocks (quadruples) that contain every triple exactly once.

Actual blocks of such a system can be seen in the La Jolla Covering Repository at this link.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ wow, sorry to have missed this! saw the condition on the Kirkman page with $n \equiv 3 \text{mod } 6$ but failed to see it would work in this case. thanks! $\endgroup$
    – Benjamin Dickman
    Commented Feb 14, 2022 at 0:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .