Families that remain kk-Sperner even after omitting an element of their ground set

preprint2012arXivOpen access

Abstract

A family $\cF\subseteq 2^{[n]}$ of sets is said to be ll-trace kk-Sperner if for any ll-subset L⊂[n]L \subset [n] the family $\cF|_L=\{F|_L:F \in \cF\}=\{F \cap L: F \in \cF\}$ is kk-Sperner, i.e. does not contain any chain of length k+1k+1. The maximum size that an ll-trace kk-Sperner family $\cF \subseteq 2^{[n]}$ can have is denoted by f(n,k,l)f(n,k,l). For pairs of integers l<kl<k, if in a family $\cG$ every pair of sets satisfies ∣∣G1∣−∣G2∣∣<k−l||G_1|-|G_2||<k-l, then $\cG$ possesses the (n−l)(n-l)-trace kk-Sperner property. Among such families, the largest one is $\cF_0=\{F\in 2^{[n]}: \lfloor \frac{n-(k-l)}{2}\rfloor+1 \le |F| \le \lfloor \frac{n-(k-l)}{2}\rfloor +k-l\}$ and also $\cF'_0=\{F\in 2^{[n]}: \lfloor \frac{n-(k-l)}{2}\rfloor \le |F| \le \lfloor \frac{n-(k-l)}{2}\rfloor +k-l-1\}$ if n−(k−l)n-(k-l) is even. In an earlier paper, we proved that this is asymptotically optimal for all pair of integers l<kl<k, i.e. $f(n,k,n-l)=(1+o(1))|\cF_0|$. In this paper we consider the case when l=1l=1, k≥2k\ge 2, and prove that $f(n,k,n-1)=|\cF_0|$ provided nn is large enough. We also prove that the unique (n−1)(n-1)-trace kk-Sperner family with size f(n,k,n−1)f(n,k,n-1) is $\cF_0$ and also $\cF'_0$ when n+kn+k is odd.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.