- What is the maximum size of a family of subsets of $[n]:=\{1,2,3,\dots,n\}$ say $\mathcal{A}$ such that $\mid A\cap B\mid \ge k$ where
$A,B\in \mathcal{A}$ and $1\le k\le n-1$?
This not Erdos-ko-rado theorem. In Erdos-ko-rado theorem, we place an extra restriction that subsets of $\mathcal{A}$ have to be of same size.
My idea:
There are $2^{n-k}$ subsets of $\{k+1,k+2,\dots ,n\}$. Append $\{1,2,\dots ,k\}$ to each of these sets. Hence, $2^{n-k}$ is a lower bound. Is it possibly the maximum we are seeking?
With some change:
2 Let $C$ be the set of subsets of $[n]$ such that size of each subset does not exceed $r$. What is the maximum size of a family of subsets from $C$ (say $\mathcal{B}$) such that $\mid A\cap B\mid \ge k$ where
$A,B\in \mathcal{B}$ and $1\le k\le r$?
Best Answer
The answer to your question is known as Katonas Theorem.
We use the following notation: Let $\mathcal{N}$ be the set of positive integers, $[i,j]=\{i,i+1,\dots,j\}$ for $i,j \in \mathcal{N}, [n] = [1,n]$ and for $k<n$ let $2^{[n]}=\{A:A\subset[n]\}$ be the unrestricted subsets of $[n]$.
A system of sets $\mathcal{A}\subset 2^{[n]}$ is called k-intersecting, if $|A_1 \cap A_2| \geq k$ for all $A_1,A_2\in \mathcal{A}$.
The answer above together with a really short proof can be found in the paper Katona's intersection theorem: Four proofs, from R. Ahlswede and L. H. Khachatrian.
Note: An interesting overview with answers to your and related questions can be found in Intersecting families of sets and permutations: a survey from Peter Borg ($2011$).
The interesting values $M(n,k) > 2^{n-k}$ $(2\leq n \leq 6$ and $1 \leq k \leq n-1)$ are written $\bf{bold}$.
The following four examples are simply for illustration. For $$(n,k)\in\{(4,2),(5,2),(5,3),(6,2)\}$$ a family $\mathcal{A}_1$ according to the appoach of talegari with $|\mathcal{A}_1|=2^{n-k}$ elements and a family $\mathcal{A}_2$ with $|\mathcal{A}_2|=M(n,k) > 2^{n-k}$ is listed.
Example: $n=4,k=2$
Example: $n=5,k=2$
Example: $n=5,k=3$
Example: $n=6,k=2$