Application of Erdős–Ko–Rado

Question

Here is an interesting question.

I believe you have to use the fact the Erdős–Ko–Rado Theorem tells you $A$ and $B$ are not intersecting, but I am unable to show it:

Let $A,B \subset[n]^{(r)}$, where $r \le \frac{n}{2}$ and $[n]^{(r)}$ is the set of all $r$ element subsets of $\{1,2,3, \cdots, n \}$

Show that if $$|A|, |B| > \binom{n-1}{r-1}$$ then there exist $a \in A$ and $b \in B$ with $a \cap b = \emptyset$.

Any help would be appreciated!

Answer 1

EDIT : There is a paper by L Pyber on this problem which also uses the cycle method. See this link

The proof I came up with uses Katona's Cycle method and the probabilistic method.
There might be a simpler proof, and I'll be interested in seeing it!

I can't immediately see how Erdős–Ko–Rado can be applied directly. Maybe I'm missing an obvious proof. (Or maybe the problem is not as easy as it seems anyways).

If you are not familiar with the Cycle Method, Katona gave a good survey paper here

In fact, I'll show a stronger result. In particular, if $$|A||B| > \binom{n-1}{r-1}^{2}$$

Then there exists $a \in A$, $b \in B$ such that

$$a \cap b = \phi$$

Claim 1
Let $A$ and $B$ be families of sets such that $A \subseteq [n]^{(r)}$ and $B \subseteq [n]^{(r)}$ and $n \ge 2r$ and for all $a \in A$ and $b \in B$ $$a \cap b \ne \phi$$ Then, $$|A||B| \le \binom{n-1}{r-1}^{2}$$ Proof (Sketch)

Pick a cyclic permutation of the numbers $\{1,2, \cdots, n \}$ , say $\sigma$, uniformly at random, also pick an index $i$ in this permutation uniformly at random, and an index $j$ in the same permutation uniformly at random. All three choices are made independently.

Starting from $i$, consider the next $r$ elements in the cycle and call it $X$ i.e. $$X = \{\sigma(i),\sigma(i+1),\sigma(i+2), \cdots, \sigma(i+r-1) \}$$

Similarly, starting from $j$, consider the next $r$ elements in the cycle and call it $Y$ i.e. $$Y = \{\sigma(j),\sigma(j+1),\sigma(j+2), \cdots, \sigma(j+r-1) \}$$

Note that

$$Pr(X \in A \mbox{ and } Y \in B) = \frac{|A|}{\binom{n}{r}} \frac{|B|}{\binom{n}{r}}$$

I also claim that

$$Pr(X \in A \mbox{ and } Y \in B) \le \frac{r^2}{n^2}$$

Combining these two gives

$$\frac{|A|}{\binom{n}{r}} \frac{|B|}{\binom{n}{r}} \le \frac{r^2}{n^2}$$

Which implies the claim. So what remains is to show that $Pr(X \in A \mbox{ and } Y \in B) \le \frac{r^2}{n^2}$

To show this I'll focus on proving a claim about the cycle itself.

---

Claim 2
Let $A$ and $B$ be sets of size $r$ formed from intervals in the cycle $\sigma$ such that $n \ge 2 r$ and for all $a \in A$ and $b \in B$, $$a \cap b \ne \phi$$ Then, $$|A|+|B| \le 2 r$$

Proof (Sketch)

Let $A^* = \{a^*_1,a^*_2,a^*_3, \cdots, a^*_n \}$ where $a^*_i$ is the interval which starts at position $i$ in $\sigma$. And $|a^*_i|=r$.
Assume WLOG that $a^*_1 \in A$ (we can relabel $\sigma$ otherwise).
Let $B^*$ be the set of all possible intervals which intersect $a^*_1$ . And let $b^*_i \in B^*$ (where $|b^*_i|=r$) be the interval which ends at position $i$ in $\sigma$ (when relabeled as above).
Note that, $$|B| \le |B^*|$$ Because $B \subseteq B^*$

Since each interval in $B^*$ must have starting or ending positions in $a_1$, we know that $$|B^*| \le (2r-1)$$ Clearly, if $|A|=1$ then $$|A|+|B| \le |A|+ |B^*| \le 1 + (2r-1) = 2r$$ Also note that, if $a^*_j \in A$ then $b^*_{j-1} \not \in B^*$ (where $2 \le j \le r$) since $a^*_j$ and $b^*_{j-1}$ cannot intersect, because $r \le \frac{n}{2}$.
So, $$|B^*| \le (2r-1) - |A \setminus a^*_1| = (2r-1) - (|A|-1)$$ Hence, $$|A|+|B| \le |A| + |B^*| \le |A| + (2r-1) - (|A|-1) = 2r$$ This immediately implies that $$|A||B| \le r^2$$

---

Claim 3
In Claim 1, the inequality $$Pr(X \in A \mbox{ and } Y \in B) \le \frac{r^2}{n^2}$$ Holds

Proof (Sketch)

This immediately follows from claim 2. Since

$$|P|+|Q| \le 2 r$$

Implies,

$$|P||Q| \le r^2$$

So, $$Pr(X \in A \mbox{ and } Y \in B) \le \frac{r^2}{n^2}$$

---

Of course some details were left out due to length of the answer, but you should be able to fill in the details since the key ideas are included.

You might also want to take a look at a proof of the Erdős–Ko–Rado Theorem by Noga Alon using a similar approach in this paper (Theorem 1.3)

Answer 2

If I did this correctly, then Hoffman's bound for crossintersecting sets will work. I am too lazy to think about the best paper to quote, so I will just refer to my own:

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p49

Look at Lemma 4 and my Tokushige's paper. That is what you want. In your case, we are looking at the disjointness graph of r-sets. So the sets are the vertices and two r-sets are adjacent if they are disjoint. This graph has $v = \binom{n}{r}$ vertices, it is $k = \binom{n-r}{r}$-regular as one $r$-set is disjoint to $\binom{n-r}{r}$ $r$-sets. The second largest absolute eigenvalue $\lambda_b$ is $\binom{n-r-1}{n-2r}$. The last value can be found in the literature (I guess, Delsarte, Association schemes and t-designs in regular semilattices, JCTA, has it).

Then Hoffman's bound, which states $$ \sqrt{|A| \cdot |B|} \leq \frac{v \cdot \lambda_b}{k + \lambda_b} $$ for this graph and your problem, shows the result.

I am not sure if this is a simple proof, as it requires much other stuff (Hoffman's bound, known eigenvalues), but it works nicely.

Answer 3

An alternative proof uses the Kruskal-Katona theorem (and is a slight modification of Daykin's beautiful proof of the Erdős-Ko-Rado theorem).

Let $C = \{ [n] \setminus a : a \in A \} \subseteq [n]^{(n-r)}$ be the family of complements of sets in $A$. Let $\partial_r C = \cup_{c \in C} \; c^{(r)}$ be the $r$-uniform shadow of $C$; that is, all $r$-sets in $[n]$ contained in some $c \in C$.

Since $|C| = |A| > \binom{n-1}{r-1} = \binom{n-1}{n-r}$, the Kruskal-Katona theorem (which lower bounds the size of a shadow) implies $|\partial_r C| > \binom{n-1}{r}$.

Now we have $B,\partial_r C \subseteq [n]^{(r)}$ with $|B| + |\partial_r C| > \binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r} = |[n]^{(r)}|$, and hence $B \cap \partial_r C \neq \emptyset$. That is, there is some $b \in B$ and $c \in C$ such that $b \subseteq c$. However, since $c = [n] \setminus a$ for some $a \in A$, it follows that $b \cap a = \emptyset$, giving the desired disjoint pair.