Sperner systems consisting of pairs of complementary subsets |
| |
Authors: | Béla Bollobás |
| |
Institution: | Department of Pure Mathematics, University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, England |
| |
Abstract: | It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if = {;A1,…, Al}; consists of k-subsets of a set with n > 2k elements such that Ai ∩ Aj ≠ ? for all i, j then l ? (k?1n?1). Schönheim proved that if A1, …, Al are subsets of a set S with n elements such that Ai ? Aj, Ai ∩ Aj ≠ ø and Ai ∪ Aj ≠ S for all i ≠ j then . In this note we prove a common strengthening of these results. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|