Two-part set systems

MaRDI QIDQ426823zbMATH OpenFDO

Authors Péter L. Erdős, Dániel Gerbner, Nathan Lemons, Dhruv Mubayi, Cory Palmer, Balázs Patkós

Publication date 12 June 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.0099, http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i1p52

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal set theoryintersectingsperner

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: The two part Sperner theorem of Katona and Kleitman states that if $X$ is an $n$-element set with partition $X_{1}cup{X}_2$, and $cF$ is a family of subsets of $X$ such that no two sets $A,BincF$ satisfy $AsubsetB$ (or $BsubsetA$) and $Acap{X}_i=Bcap{X}_i$ for some $i$, then $|cF|lenchooselfloorn/2floor$. We consider variations of this problem by replacing the Sperner property with the intersection property and considering families that satisfiy 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 $cF,cG$ be families of subsets of an $n$-element set such that $cF$ and $cG$ are both intersecting and cross-Sperner, meaning that if $AincF$ and $BincG$, then $AotsubsetB$ and $BotsubsetA$. Then $|cF|+|cG|<2^{n-1}$ and there are exponentially many examples showing that this bound is tight.

Recommendations

• All maximum 2-part Sperner families
• All Maximum Size Two-Part Sperner Systems: In Short
• Publication:3496336
• On the structure of maximum 2-part Sperner families
• Even and odd pairs of lattice paths with multiple intersections

Cited in

(8)

• Improved bounds for cross-Sperner systems
• Even and odd pairs of lattice paths with multiple intersections
• A Sperner-type theorem for set-partition systems
• Clique number of Xor products of Kneser graphs
• Systems of sets of lengths. II
• Sperner partition systems
• All Maximum Size Two-Part Sperner Systems: In Short
• All maximum 2-part Sperner families

This page was built for publication: Two-part set systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426823)