Let $\mathcal F$ be a collection of all subsets of $[n]$ so that each two subsets have a common element and are same size of $k$ ($n \ge 2k$). Prove that $|\mathcal F| \le {n - 1 \choose k - 1}$. I have been able to prove that if all those subsets have a common ellement then $\mathcal F = {n-1 \choose k-1}$. But I am struggling with the rest of the problem. Can someone please help?


closed as off-topic by Aqua, Leucippus, Namaste, Moishe Kohan, Demophilus Nov 12 '17 at 1:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Aqua, Leucippus, Namaste, Moishe Kohan, Demophilus
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What set is [n]? It looks like a modulo class. But of what? [n] = { n + j*M} but what is M? And what is k. n >= 2k???? what is k? $\endgroup$ – fleablood Nov 11 '17 at 16:35
  • 1
    $\begingroup$ This is the famous Erdos-Ko-Rado Theorem. There is a very short, nice proof with the probabilistic method. $\endgroup$ – jlammy Nov 11 '17 at 16:37
  • $\begingroup$ [N] is a set of n elements $\endgroup$ – Luka Markovic Nov 11 '17 at 16:42
  • $\begingroup$ "A collection, F, of $k \in X$, so that each two in F have a property". Doesn't actually make any sense. You can't collect all of something with a property that will depend upon which of the things you collect. If I try to select all sets with 1 element so that any two have an elment in common, the I can only pick 1 set, but which one depends upon... which one I pick. So I can't select all of them (because then any two will not have an element in common. $\endgroup$ – fleablood Nov 11 '17 at 16:43
  • $\begingroup$ Not, "all" subsets of $[n]$ but a collection of some subsets of [n] so that that condition is met. By the way, I have never seen the notation [n] to mean a set of n elements before in my life. $\endgroup$ – fleablood Nov 11 '17 at 16:45

Lemma. Consider sets $S_j=\{j,j+1,\dots,j+k-1\}$, with addition mod $n$ and $0\leq j\leq n-1$. Then at most $k$ of the $S_j$ are in $\mathcal F$.

Proof. Take some $S_{\ell}\in\mathcal F$. Any other $S_j$ with $S_j\cap S_{\ell}\neq\emptyset$ can be partitioned into $k-1$ pairs $(S_{\ell-j},S_{\ell+k-j})$ with $S_{\ell-j}\cap S_{\ell+k-j}=\emptyset$. The result now follows. $\square$

Now choose a permutation $\pi$ of $\{0,1,\dots,n-1\}$ and some $0\leq i\leq n-1$, at random and independently. Let $S=\{\pi(i),\pi(i+1),\dots,\pi(i+k-1)\}$, with addition mod $n$. Conditioning on $\pi$, by our lemma, $\mathbb P(S\in\mathcal F)\leq\frac{k}{n}$, so $$\frac{k}{n}\geq\mathbb P(S\in\mathcal F)=\frac{|\mathcal F|}{\binom{n}{k}}\implies|\mathcal F|\leq\binom{n-1}{k-1}.$$


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