suppose that $\mathcal F\subseteq X^{(k)}$ and $|X|=n$. we know that for every three distinct elements of $\mathcal F$ like $A,B,C$, at most one of $A\cap B$,$B\cap C$ and $C\cap A$ is $\phi$. for $k\le \frac{n}{2}$ prove that: a) $|\mathcal F|\le max(1,4-\frac{n}{k})\times \dbinom{n-1}{k-1}$.(15 points) b) find all cases of equality in a) for $k\le \frac{n}{3}$.(5 points)
Problem
Source:
Tags: combinatorics proposed, combinatorics
16.03.2011 20:00
Clearly, it has a lot to do with the Erdös-Ko-Rado theorem.
16.03.2011 20:22
would you please post your solution? I'll be glad to see it. Thanks
31.05.2017 12:08
a) WLOG let $X=\{1,...,n\}$ 1 case: All the intersections are nonempty - then by Erdos-Ko-Rado $|F| \le \dbinom{n-1}{k-1}.$ 2 case: $\exists i,j$ s.t $A_i \cap A_j=\emptyset.$ Notice that, then $\forall t \neq i,j$ we have $A_t \cap A_i \neq \emptyset$ and $A_t \cap A_j \neq \emptyset.$ Now, consider random permutation $\pi$ of set $X$ and arrange $\pi(1),...,\pi(n)$ on circle by clockwise order. Consider some random set $P$ generated by random $i$ s.t $P=\{\pi(i),...,\pi(k+i-1) \}.$ Let's count now the number of elements of $F$ on circle such that they contain $k$ consecutive numbers (label it by $u$ and call such sets good). 2.1 If on the circle there are no good sets with empty intersection, we have $u \le k.$ So if we let $\mathbb P$ be the probability that $P \in F,$ then $$\mathbb P=\frac{|F|}{\dbinom{n}{k}} \le \frac{k}{n}$$so it follows that $|F| \le \dbinom{n-1}{k-1}. (*)$ 2.2 If there are good sets with empty intersections, let them be $A_i, A_j.$ By previous, any $A_t$ must have non-empty intersection with both of them. Let the one distance between endpoints of $A_i, A_j$ be $a$ and let the other one be $b.$ Clearly, $a+b=n-2k$ i.e $(k-a)+(k-b)=4k-n.$ On the other hand, we must have $u \le (k-a-1)+(k-b-1)+2 = 2k-(a+b)=4k-n.$ Hence, as in 2.1 we have $$\mathbb P=\frac{|F|}{\dbinom{n}{k}} \le \frac{4k-n}{n}=\frac{k}{n}\cdot (4-\frac{n}{k}) \implies |F| \le (4-\frac{n}{k}) \cdot \dbinom{n-1}{k-1} (**)$$So, from $(*),(**)$ result follows. $\blacksquare$