5
$\begingroup$
  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$?

$\endgroup$
1
  • $\begingroup$ Related to: 833017 $\endgroup$ Commented Jun 13, 2014 at 15:47

2 Answers 2

Reset to default
4
+50
$\begingroup$

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*}

$\endgroup$
2
  • 1
    $\begingroup$ @talegari: Thanks for the bounty! I've added some small examples for better illustration. Best regards, $\endgroup$ Commented Jul 19, 2014 at 20:37
  • $\begingroup$ Thanks for your answer. I could not have asked for more. $\endgroup$ Commented Jul 21, 2014 at 3:13
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ +1 Thanks for your answer. Most of the problems discusses in the paper seem to concern the family of subsets from $\binom{[n]}{k}$ and not the set of all subsets. $\endgroup$ Commented Jul 18, 2014 at 10:25

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.