The Electronic Journal of Combinatorics · 2005 · 36 citations · 5 references
Natural SciencesComputer ScienceMathematicsCombinatoricsDiscrete MathematicsSet TheoryCombinatorial Number TheoryCombinatorial Set TheorySet SystemsErdős - Ko - Rado TheoryErdős - Rado TheoremsErdős-ko-rado TheoremErdős-rado TheoremIntersection TheoremsRado's TheoremSet Partitions
Two set partitions of an $n$-set are said to $t$-intersect if they have $t$ classes in common. A $k$-partition is a set partition with $k$ classes and a $k$-partition is said to be uniform if every class has the same cardinality $c=n/k$. In this paper, we prove a higher order generalization of the Erdős-Ko-Rado theorem for systems of pairwise $t$-intersecting uniform $k$-partitions of an $n$-set. We prove that for $n$ large enough, any such system contains at most $${1\over(k-t)!} {n-tc \choose c} {n-(t+1)c \choose c} \cdots {n-(k-1)c \choose c}$$ partitions and this bound is only attained by a trivially $t$-intersecting system. We also prove that for $t=1$, the result is valid for all $n$. We conclude with some conjectures on this and other types of intersecting partition systems.
5
Intersection Theorems for Systems of Sets
P. Erdös, R. Rado · Journal of the London Mathematical Society · 1960 · 638 citations