Families that remain \(k\)-Sperner even after omitting an element of their ground set

Balázs Patkós¹

¹Alfred Renyi Institute of Mathematics

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

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

Détail

DOI : 10.37236/2543

Classification : 05D05
Mots-clés : extremal set systems, chains, traces