4
$\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$
    – talegari
    Jun 13, 2014 at 15:47

2 Answers 2

2
+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$
    – epi163sqrt
    Jul 19, 2014 at 20:37
  • $\begingroup$ Thanks for your answer. I could not have asked for more. $\endgroup$
    – talegari
    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$
    – talegari
    Jul 18, 2014 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.