Induced and non-induced forbidden subposet problems

Balázs Patkós¹

¹Alfred Renyi Institute of Mathematics

The electronic journal of combinatorics, Tome 22 (2015) no. 1

Résumé

The problem of determining the maximum size $La(n,P)$ that a $P$-free subposet of the Boolean lattice $B_n$ can have, attracted the attention of many researchers, but little is known about the induced version of these problems. In this paper we determine the asymptotic behavior of $La^*(n,P)$, the maximum size that an induced $P$-free subposet of the Boolean lattice $B_n$ can have for the case when $P$ is the complete two-level poset $K_{r,t}$ or the complete multi-level poset $K_{r,s_1,\dots,s_j,t}$ when all $s_i$'s either equal 4 or are large enough and satisfy an extra condition. We also show lower and upper bounds for the non-induced problem in the case when $P$ is the complete three-level poset $K_{r,s,t}$. These bounds determine the asymptotics of $La(n,K_{r,s,t})$ for some values of $s$ independently of the values of $r$ and $t$.

Détail

DOI : 10.37236/4644

Classification : 05D05, 05C35, 05C25, 06A07
Mots-clés : extremal set systems, forbidden subposets