1. A Proof and Generalizations of the Erdős-Ko-Rado Theorem Using the Method of Linearly Independent Polynomials.
- Author
-
Graham, R. L., Korte, B., Lovász, L., Wigderson, A., Ziegler, G. M., Klazar, Martin, Kratochvíl, Jan, Loebl, Martin, Matoušek, Jiří, Valtr, Pavel, Thomas, Robin, Füredi, Zoltán, Hwang, Kyung-Won, and Weichsel, Paul M.
- Abstract
Our aim is to exhibit a short algebraic proof for the Erdös-Ko-Rado theorem. First, we summarize the method of linearly independent polynomials showing that if X1,..., Xm ⊂ [n] are sets such that Xi does not satisfy any of the set of s intersection conditions Ri but Xi satisfies at least one condition in Rj for all j > i then $$ m \leqslant \left( {\begin{array}{*{20}c} n \\ s \\ \end{array} } \right) + \left( {\begin{array}{*{20}c} n \\ {s - 1} \\ \end{array} } \right) + \cdot \cdot \cdot + \left( {\begin{array}{*{20}c} n \\ 0 \\ \end{array} } \right) $$. The EKR theorem is follows by carefully choosing the intersection properties and adding extra polynomials. We also prove generalizations for non-uniform families with various intersection conditions. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF