Let $S=\{1,2,\ldots,n\}$. Let $A_i\subset S$ for $i\in\{1,2,\ldots,m\}$. Impose the following conditions
- $|A_i|=r$ with $r<n$ for all $i$.
- $|A_i\cap A_j|=t$ for all $i\neq j$, with $t<r$.
Let $n,r,t$ be fixed. What is the maximum number $m$ of subsets $A_i$ that satisfy these conditions?
The question arises from my observation of a game called Rafly, where there are 55 cards, each with 8 images on them. No matter which 2 cards you pick, they have one and only one common image. I want to generalize this game by using the minimum number of $n$ images, having $m$ cards, each with $r$ images and $t$ common images. However, I am having trouble with finding $m$ given $n,r$ and $t$.
In the case of $t=1$ I start to build the cards like this:
$$A_1 = \{1,2,\ldots,r\}.$$
A new card must have one common element with the first card:
$$A_2 = \{c_{1,2}, r+1,\ldots, 2r-1 \},$$
where $c_{1,2}\in A_1$. A new card must have one common element with the second and first cards:
$$A_3 = \{c_{1,3},c_{2,3}, 2r,2r+1,\ldots, 3r-3\},$$
where $c_{1,3}\in A_1$ and $c_{2,3}\in A_2\setminus A_1$. Following this reasoning I conclude that there are $n=r(r+1)/2$ different images. But how many cards are there? How are these quantities related to $t$? Thanks a lot.
Best Answer
Your problem in the $t=1$ case was asked here. I will provide a generalization of those ideas to your problem.
There are $\binom{n}{t+1}$ subsets of $S$ with size $t+1$. Each set $A_i$ has $\binom{r}{t+1}$ subsets of size $t+1$. Furthermore, the $\binom{r}{t+1}$ subsets of size $t+1$ for $A_i$ must be different then those for $A_j$, because $A_i$ and $A_j$ only have $t$ elements in common. Therefore, counting up the total number of subsets of size $t+1$ found in some set $A_i$, we get $$ m\cdot\binom{r}{t+1}\le \binom{n}{t+1} $$ This give you an upper bound on $m$.
If equality is attained, this would mean that every subset of size $t+1$ is contained in exactly one set $A_i$. . This means that you have a Steiner system $S(t+1,r,n)$. Not much is known about when Steiner systems exist; see the other answer for some more information.