maximum size of a $k$-intersecting family of $[n]$

1. 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$?

Solution 1:

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}$.

Theorem (Katona $1964$):

Let $I(n,k)$ denote the set of all $k$-intersecting systems and $M(n,k)=max_{\mathcal{A}\in I(n,k)}|\mathcal{A}|$. The following statement is valid

\begin{equation*} M(n,k)= \begin{cases}\sum_{j=\frac{n+k}{2}}^{n}\binom{n}{j},&2 \mid (n+k)\\ &\\ 2\sum_{j=\frac{n+k-1}{2}}^{n-1}\binom{n-1}{j},&2 \nmid (n+k) \end{cases} \end{equation*}

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$).

Added 2014-07-19: I've added below a table and examples for small values $M(n,k)$ with $n \leq 6$ to provide a first impression which $k$-intersecting families $\mathcal{A}$ have size $|\mathcal{A}| > 2^{n-k}$.

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}$.

$M(n,k)$:

\begin{align*} \begin{array}{crrrrr} n/k&1&2&3&4&5\\ \hline\\ 2&2\\ 3&4&2\\ 4&8&\bf{5}&2\\ 5&16&\bf{10}&\bf{6}&2\\ 6&32&\bf{22}&\bf{12}&\bf{7}&2 \end{array} \end{align*}

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$

$|\mathcal{A}_1|=2^{4-2}=4$, $|\mathcal{A}_2|=M(4,2)=5$

\begin{align*} \begin{array}{rl} \mathcal{A}_1=&\{\{1,2\},\\ &\{1,2,3\},\{1,2,4\},\\ &\{1,2,3,4\}\}\\ \end{array} \qquad \begin{array}{rl} \mathcal{A}_2=&\{\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\\ &\{1,2,3,4\}\}\\ \\ \end{array} \end{align*}

Example: $n=5,k=2$

$|\mathcal{A}_1|=2^{5-2}=8$, $|\mathcal{A}_2|=M(5,2)=10$

\begin{align*} \begin{array}{rl} \mathcal{A}_1=&\{\{1,2\},\\ &\{1,2,3\},\{1,2,4\},\{1,2,5\},\\ &\{1,2,3,4\},\{1,2,3,5\},\{1,2,4,5\},\\ &\{1,2,3,4,5\}\}\\ \end{array} \begin{array}{rl} \mathcal{A}_2=&\{\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\\ &\{1,2,3,4\},\{1,2,3,5\},\{1,2,4,5\},\\ &\{1,3,4,5\},\{2,3,4,5\},\\ &\{1,2,3,4,5\}\}\\ \end{array} \end{align*}

Example: $n=5,k=3$

$|\mathcal{A}_1|=2^{5-3}=4$, $|\mathcal{A}_2|=M(5,3)=6$

\begin{align*} \begin{array}{rl} \mathcal{A}_1=&\{\{1,2,3\},\\ &\{1,2,3,4\},\{1,2,3,5\},\\ &\{1,2,3,4,5\}\}\\ \end{array} \begin{array}{rl} \mathcal{A}_2=&\{\{1,2,3,4\},\{1,2,3,5\},\{1,2,4,5\},\\ &\{1,3,4,5\},\{2,3,4,5\},\\ &\{1,2,3,4,5\}\}\\ \end{array} \end{align*}

Example: $n=6,k=2$

$|\mathcal{A}_1|=2^{6-2}=16$, $|\mathcal{A}_2|=M(6,2)=22$

\begin{align*} \mathcal{A}_1=\{&\{1,2\},\\ &\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,2,6\},\\ &\{1,2,3,4\},\{1,2,3,5\},\{1,2,3,6\},\\ &\{1,2,4,5\},\{1,2,4,6\},\{1,2,5,6\}\\ &\{1,2,3,4,5\},\{1,2,3,4,6\},\{1,2,3,5,6\},\{1,2,4,5,6\},\\ &\{1,2,3,4,5,6\}\}\\ \\ \mathcal{A}_2=\{&\{1,2,3,4\},\{1,2,3,5\},\{1,2,3,6\},\{1,2,4,5\},\{1,2,4,6\},\\ &\{1,2,5,6\},\{1,3,4,5\},\{1,3,4,6\},\{1,3,5,6\},\{1,4,5,6\},\\ &\{2,3,4,5\},\{2,3,4,6\},\{2,3,5,6\},\{2,4,5,6\},\{3,4,5,6\},\\ &\{1,2,3,4,5\},\{1,2,3,4,6\},\{1,2,3,5,6\},\\ &\{1,2,4,5,6\},\{1,3,4,5,6\},\{2,3,4,5,6\}\\ &\{1,2,3,4,5,6\}\}\\ \end{align*}

Solution 2:

This is one of the classical problems in Extremal Set Theory, with Erdos-Ko-Rado theorem addressing the simplest case. Infact, as per my knowledge, this was the problem Erdos had in mind. Ofcourse there is no simple combinatorial solution yet(and probably won't be a $simple$ one). This paper will shed some light on its complexity.