Forbidding rank-preserving copies of a poset


الملخص بالإنكليزية

The maximum size, $La(n,P)$, of a family of subsets of $[n]={1,2,...,n}$ without containing a copy of $P$ as a subposet, has been intensively studied. Let $P$ be a graded poset. We say that a family $mathcal{F}$ of subsets of $[n]={1,2,...,n}$ contains a emph{rank-preserving} copy of $P$ if it contains a copy of $P$ such that elements of $P$ having the same rank are mapped to sets of same size in $mathcal{F}$. The largest size of a family of subsets of $[n]={1,2,...,n}$ without containing a rank-preserving copy of $P$ as a subposet is denoted by $La_{rp}(n,P)$. Clearly, $La(n,P) le La_{rp}(n,P)$ holds. In this paper we prove asymptotically optimal upper bounds on $La_{rp}(n,P)$ for tree posets of height $2$ and monotone tree posets of height $3$, strengthening a result of Bukh in these cases. We also obtain the exact value of $La_{rp}(n,{Y_{h,s},Y_{h,s}})$ and $La(n,{Y_{h,s},Y_{h,s}})$, where $Y_{h,s}$ denotes the poset on $h+s$ elements $x_1,dots,x_h,y_1,dots,y_s$ with $x_1<dots<x_h<y_1,dots,y_s$ and $Y_{h,s}$ denotes the dual poset of $Y_{h,s}$.

تحميل البحث