Erdős-Ko-Rado theorems for uniform set-partition systems

Karen Meagher, Lucia Moura

The Electronic Journal of Combinatorics · 2005 · 36 citations · 5 references

DOIFull text

Open access

Concepts

Abstract

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.

References

5