Extremal problems concerning Kneser-graphs (Q1057858): Difference between revisions

Let A and B be two intersecting families of k-subsets of an n-element set. It is proved that \(| A\cup B| \leq \left( \begin{matrix} n-1\\ k- 1\end{matrix} \right)+\left( \begin{matrix} n-2\\ k-1\end{matrix} \right)\) holds for \(n>(3+\sqrt{5})k.\) Equality holds only if there exist two elements a,b such that \(\{a,b\}\cap F\neq \emptyset\) for all \(F\in A\cup B\). For \(n=2k+o(\sqrt{k})\) an example shows that \(\max | A\cup B| =(1- o(1))\left( \begin{matrix} n\\ k\end{matrix} \right).\) Another result is: If \(F_ 1,....,F_ r\) is a partition of the set of all k-element sets of an n-set and \(r\leq n/t-k^ 4\) then there exists an i (1\(\leq i\leq r)\) such that \(F_ i\) contains more than t pairwise disjoint members. Very recently N. Alon, P. Frankl and L. Lovász proved that the same holds for \(n>rt+(k-1)(t+1)\) and this bound is the best possible.