A set of subsets of the set $\{1,2,\ldots,n\}$ is to be created in the following way : for a certain integer $r$ such that $n \geq r$,
- Each element of $\{1,2,3,\ldots,n\}$ can be present in at most $r$ sets.
- The size of each subset is also equal to $r$.
How can one find such a collection of sets which has the largest size? Please note that I am taking $n \geq r$.
Example : Take $\{1,2,3,4\}$ (i.e. $n=4$) and each element can be present in at most $2$ sets so that $r=2$. We obtain $\{1,2\},\{1,3\},\{2,4\},\{3,4\}$ as the answer.
I don't know how to generalize this to larger $n$ and $r$.
Please tell me how to approach this.
I did this using graph theory approach. But I was not sure of the exact number of sets. I defined a bipartite graph with left side as 1 to n with degree almost r and right side vertices of graph as some s with degree r. This gave me $nr\geq sr \implies s \leq n$. But I was thinking of a certain number. *Is there any possible relation between s and $r^2$ is what I was looking for! Any thoughts?
The largest possible number of sets is $n$. This can be obtained by taking the $n$ cyclic rotations of the set $\{1,\dots,r\}$.
This is best explained with an example. When $n=8$ and $r=5$, here is a collection of $8$ subsets, each with size $5$, such that every element appears in at most $5$ subsets. $$ \{1,2,3,4,5\}\\ \{2,3,4,5,6\}\\ \{3,4,5,6,7\}\\ \{4,5,6,7,8\}\\ \{5,6,7,8,1\}\\ \{6,7,8,1,2\}\\ \{7,8,1,2,3\}\\ \{8,1,2,3,4\}\\ $$ It should be clear that $n$ subsets is the best possible number. If you have $s$ subsets each with size $r$, then the total number of elements in all subsets, counted with repeats, is $r\cdot s$. On average, that means each element of $\{1,\dots,n\}$ appears in $r\cdot s/n$ subsets. Since we require each element to appear in at most $r$ subsets, this average must be at most $r$, which implies $r\cdot s/n\le r$, which implies $s\le n$.