A Sperner-Type Theorem for Set-Partition Systems
A Sperner-Type Theorem for Set-Partition Systems
复制标题
集合划分系统的斯佩尔纳型定理
DOI：
10.37236/1987
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
B. Stevens
中科院分区：
文献类型：
--
作者：
Karen Meagher;Lucia Moura;B. Stevens
Sperner分拆系统是一个集合分拆系统，使得系统中的任何两个集合分拆$P$和$Q$具有这样的性质：对于$P$的所有类$A$和$Q$的所有类$B$，$A \not\subseteq B$和$B \not\subseteq A$。一个$k$-划分是一个有$k$类的集合划分，一个$k$-划分被称为均匀划分，如果每个类都有相同的基数$c=n/k$。本文证明了Sperner定理的一个高阶推广。特别地，我们证明了如果$k$整除$n$，则$n$-集上的最大Sperner $k$-划分系统具有基数${n-1 \choose n/k-1}$，并且是一致划分系统。本文给出了任意k和n的n-集的Sperner k-分拆系统的基数的一个界。
A Sperner partition system is a system of set partitions such that any two set partitions $P$ and $Q$ in the system have the property that for all classes $A$ of $P$ and all classes $B$ of $Q$, $A \not\subseteq B$ and $B \not\subseteq A$. 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 Sperner's Theorem. In particular, we show that if $k$ divides $n$ the largest Sperner $k$-partition system on an $n$-set has cardinality ${n-1 \choose n/k-1}$ and is a uniform partition system. We give a bound on the cardinality of a Sperner $k$-partition system of an $n$-set for any $k$ and $n$.