Two-part set systems

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

extremal set theory intersecting sperner

Abstract: The two part Sperner theorem of Katona and Kleitman states that if

X

is an

n

-element set with partition

X_{1} c u p X_{2}

, and

c F

is a family of subsets of

X

such that no two sets

A, B i n c F

satisfy

A s u b s e t B

(or

B s u b s e t A

) and

A c a p X_{i} = B c a p X_{i}

for some

i

, then

| c F | l e n c h o o s e l f l o o r n / 2 f l o o r

. 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

c F, c G

be families of subsets of an

n

-element set such that

c F

and

c G

are both intersecting and cross-Sperner, meaning that if

A i n c F

and

B i n c G

, then

A o t s u b s e t B

and

B o t s u b s e t A

. Then

| c F | + | c G | < 2^{n - 1}

and there are exponentially many examples showing that this bound is tight.

Review text

Summary: 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 \(\mathcal{F}\) is a family of subsets of \(X\) such that no two sets \(A, B \in \mathcal{F}\) satisfy \(A \subset B (or B \subset A)\) and \(A \cap X_i=B\cap X_i\) for some \(i\), then \(|\mathcal{F}| \leq {n \choose \lfloor n/2\rfloor}\). 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 \(\mathcal{F},\mathcal{G}\) be intersecting families of subsets of an \(n\)-element set that are additionally cross-Sperner, meaning that if \(A \in\mathcal{F}\) and \(B \in \mathcal{G}\), then \(A \not\subset B\) and \(B \not\subset A\). Then \(|\mathcal{F}| +|\mathcal{G}| \leq 2^{n-1}\) and there are exponentially many examples showing that this bound is tight.

Recommendations

Cited in

(8)

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)