How many subsets of size $n+1$ can we have so no two of them have intersection of size $n$ Suppose we have a set of size $m$. How many sets of fixed size $n+1$ can we have so that no two of them have an intersection of size $n$ ?
 A: Build all subsets, where each contains $n$ out of $m-k$ elements: $\binom{m-k}{n}$.
The maximum number of elements shared by any pair of subsets is $n-1$.
Take the remaining $k$ elements, and add one (unique) element to each subset.
The maximum number of elements shared by any pair of subsets is still $n-1$.

Now, in order for this method to yield the maximum number of subsets:


*

*Find the value of $k$ for which $\min[k,\binom{m-k}{n}]$ is maximal

*As you can see, possible values of $k$ are in the range $[1,m-n]$

*Hence, the maximum number of subsets is $\max[\min[k,\binom{m-k}{n}]]$ for $k\in[1,m-n]$



A few examples:


*

*If $m-n=1$:

*

*$k=1\implies\min[k,\binom{m-k}{n}]=\min[1,\frac{(m-1)!}{n!(m-1-n)!}]=\min[1,\frac{(n+0)!}{n!0!}]=\min[1,1]=1$


*If $m-n=2$:

*

*$k=1\implies\min[k,\binom{m-k}{n}]=\min[1,\frac{(m-1)!}{n!(m-1-n)!}]=\min[1,\frac{(n+1)!}{n!1!}]=\min[1,n+1]=1$

*$k=2\implies\min[k,\binom{m-k}{n}]=\min[2,\frac{(m-2)!}{n!(m-2-n)!}]=\min[1,\frac{(n+0)!}{n!0!}]=\min[1,1]=1$


*If $m-n=3$:

*

*$k=1\implies\min[k,\binom{m-k}{n}]=\min[1,\frac{(m-1)!}{n!(m-1-n)!}]=\min[1,\frac{(n+2)!}{n!2!}]=\min[1,\frac{\dots}{2!}]=1$

*$k=2\implies\min[k,\binom{m-k}{n}]=\min[2,\frac{(m-2)!}{n!(m-2-n)!}]=\min[2,\frac{(n+1)!}{n!1!}]=\min[2,n+1]=2$

*$k=3\implies\min[k,\binom{m-k}{n}]=\min[3,\frac{(m-3)!}{n!(m-3-n)!}]=\min[3,\frac{(n+0)!}{n!0!}]=\min[3,1]=1$


*If $m-n=4$:

*

*$k=1\implies\min[k,\binom{m-k}{n}]=\min[1,\frac{(m-1)!}{n!(m-1-n)!}]=\min[1,\frac{(n+3)!}{n!3!}]=\min[1,\frac{\dots}{3!}]=1$

*$k=2\implies\min[k,\binom{m-k}{n}]=\min[2,\frac{(m-2)!}{n!(m-2-n)!}]=\min[2,\frac{(n+2)!}{n!2!}]=\min[2,\frac{\dots}{2!}]=2$

*$k=3\implies\min[k,\binom{m-k}{n}]=\min[3,\frac{(m-3)!}{n!(m-3-n)!}]=\min[3,\frac{(n+1)!}{n!1!}]=\min[3,n+1]=2$ to $3$

*$k=4\implies\min[k,\binom{m-k}{n}]=\min[4,\frac{(m-4)!}{n!(m-4-n)!}]=\min[4,\frac{(n+0)!}{n!0!}]=\min[4,1]=1$


*If $m-n=5$:

*

*$k=1\implies\min[k,\binom{m-k}{n}]=\min[1,\frac{(m-1)!}{n!(m-1-n)!}]=\min[1,\frac{(n+4)!}{n!4!}]=\min[1,\frac{\dots}{4!}]=1$

*$k=2\implies\min[k,\binom{m-k}{n}]=\min[2,\frac{(m-2)!}{n!(m-2-n)!}]=\min[2,\frac{(n+3)!}{n!3!}]=\min[2,\frac{\dots}{3!}]=2$

*$k=3\implies\min[k,\binom{m-k}{n}]=\min[3,\frac{(m-3)!}{n!(m-3-n)!}]=\min[3,\frac{(n+2)!}{n!2!}]=\min[3,\frac{\dots}{2!}]=3$

*$k=4\implies\min[k,\binom{m-k}{n}]=\min[4,\frac{(m-4)!}{n!(m-4-n)!}]=\min[4,\frac{(n+1)!}{n!1!}]=\min[4,n+1]=2$ to $4$

*$k=5\implies\min[k,\binom{m-k}{n}]=\min[5,\frac{(m-5)!}{n!(m-5-n)!}]=\min[5,\frac{(n+0)!}{n!0!}]=\min[5,1]=1$


A: A different perspective: Consider a regular graph of $\binom{m}{n+1}$ vertices and degree $(n+1)(m-n-1)$. We identify an vertex with a $n+1$ element subset of $[m]$ and a pair of vertices $v_1$ and $v_2$have an edge between them if $|v_1\cap v_2|=n$. We are looking for the length of maximum independent set in this graph.
