Abstract | ||
---|---|---|
The two part Sperner theorem of Katona and Kleitman states that if X is an n-element set with partition X-1 boolean OR X-2, and F is a family of subsets of X such that no two sets A, B is an element of F satisfy A subset of B (or B subset of A) and A boolean AND X-i = B boolean AND X-i for some i, then vertical bar F vertical bar <= ((n) left perpendicularn/2right perpendicular). We consider variations of this problem by replacing the Sperner property with the intersection property and considering families that satisfy various combinations of these properties on one or both parts X-1, X-2. Along the way, we prove the following new result which may be of independent interest: let F,G be intersecting families of subsets of an n-element set that are additionally crossSperner, meaning that if A is an element of F and B is an element of G, then A not subset of B and B not subset of A. Then vertical bar F vertical bar + vertical bar G vertical bar <= 2(n-1) and there are exponentially many examples showing that this bound is tight. |
Year | Venue | Keywords |
---|---|---|
2012 | ELECTRONIC JOURNAL OF COMBINATORICS | extremal set theory,Sperner,intersecting |
Field | DocType | Volume |
Family of sets,Discrete mathematics,Combinatorics,Partition (number theory),Mathematics | Journal | 19 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 0 |
PageRank | References | Authors |
0.34 | 3 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Péter L. Erdös | 1 | 267 | 46.75 |
Dániel Gerbner | 2 | 46 | 21.61 |
Nathan Lemons | 3 | 67 | 9.49 |
Dhruv Mubayi | 4 | 579 | 73.95 |
Cory Palmer | 5 | 44 | 10.33 |
Balázs Patkós | 6 | 85 | 21.60 |