1

Suppose $A$ is a set of $r$ combinations of an $n$ set, with $\alpha \cap \beta \neq \phi$, whenever $\alpha, \beta \in A$. Show that $$|A| \leq \binom{n-1}{r-1}$$ if $r \leq \frac n2$.

What does this question mean exactly ? Is it the set of all $r$ combinations, such that no two of them are mutually disjoint ?

The hint said to consider $\partial^{n-2r}B$, where $B$ is the set of complements of $A$. I don't know how to apply partial differentiation to combinatorics. Please help.

Andrés E. Caicedo
  • 79,201
Saikat
  • 2,461

1 Answers1

2

Let $A=\{A_1,\ldots,A_s\}$ be a family of subsets of $\{1,\ldots,n\}$. Then, $A$ is said to be an intersecting family if any two elements in $A$ have a nontrivial intersection. If we also place the restriction that all subsets in $A$ have the same cardinality, say $A$ is an intersecting family of $r$-subsets of $\{1,\ldots,n\}$ , then how large can $A$ be?

One way to generate an intersecting family of $r$-subsets of $\{1,\ldots,n\}$ is to pick an element, say $1$, to include in each of the $r$-subsets. The remaining $r-1$ elements can be chosen in ${n-1 \choose r-1}$ ways. Thus, there exists an intersecting family of $r$-subsets of $\{1,\ldots,n\}$ of cardinality ${n-1 \choose r-1}$, namely the set of all $r$-subsets which contain the element $1$. The Erdos-Ko-Rado theorem asserts that this value is the maximal size of an intersecting family of $r$-subsets and that every intersecting family of $r$-subsets of maximal size is exactly of the form just mentioned: the set of all $r$-subsets which contain one particular element.

The symbol $\partial$ is probably the notation for something like the shadow (not the partial derivative). You can look at your reference (or a text on set-systems) for the exact definition.

Ashwin Ganesan
  • 4,045
  • 11
  • 10
  • Wow. Thanks. I'll need some time to read and understand this. Now, I understood why $\binom{n-1}{r-1}$ is a possible enumeration of intersecting subsets. But, how to prove that this is the maximum number ? – Saikat Jun 26 '16 at 11:50
  • Do you have a lot of experience with combinatorics ? – Saikat Jun 26 '16 at 11:51
  • Your Eleanor definition helped me understand. Can you explain what the condition $n \gt 2r$ has to do with it ? – Saikat Jun 26 '16 at 12:00
  • *elegant ${}{}$ – Saikat Jun 26 '16 at 12:15
  • 1
    If $r > n/2$, then an $r$-subset contains more than half of the elements of ${1,\ldots,n}$ and so any two $r$-subsets will intersect. Hence, the maximal size of an intersecting family of $r$-subsets is trivially ${n \choose r}$. So the $r > n/2$ case is trivial. – Ashwin Ganesan Jun 26 '16 at 14:57
  • For a proof that that is the maximal number, you can look anywhere for a proof of the so-called Erdos-Ko-Rado theorem. – Ashwin Ganesan Jun 26 '16 at 14:59
  • What's an Eleanor definition? – Ashwin Ganesan Jun 26 '16 at 15:00
  • I already clarified I meant elegant definition. By the way, what is your mathematical background ? – Saikat Jun 26 '16 at 15:24
  • This terminology (of intersecting families) can be found in the text titled "Combinatorics: set systems, hypergraphs, families of vectors and combinatorial probability" (by Bollobas, 1986). – Ashwin Ganesan Jun 26 '16 at 15:38
  • Do you know what the partial differentiator operator means in this case ? – Saikat Jun 26 '16 at 16:42
  • @user230452: See the answer to this question. – Brian M. Scott Jun 26 '16 at 20:49
  • @BrianM.Scott I don't see any direct link between that question and mine. Please elaborate. – Saikat Jun 27 '16 at 01:45
  • @AshwinGanesan Thanks. Bollobos really is a good mathematician ! Are you also a mathematician ? – Saikat Jun 27 '16 at 01:46
  • @user230452: I was answering your question immediately above my comment. The answer in question explains the $\partial$ notation for the shadow. – Brian M. Scott Jun 27 '16 at 01:48
  • I finally have understood what a shadow is. Can you tell me how to reconcile the hint given with the proof ? – Saikat Jul 17 '16 at 15:57