Forbidden subposet problems for traces of set families

Abstract

In this paper we introduce a problem that bridges forbidden subposet and forbidden subconfiguration problems. The sets $F_1,F_2,\dots ,F_{|P|}$ form a copy of a poset $P$, if there exists a bijection $i:P\to \{F_1,F_2,\dots ,F_{|P|}\}$ such that for any $p,p^{\prime }\in P$ the relation $p{<}_P{p}^{\prime }$ implies $i(p)⊊i(p^{\prime })$. A family $\mathcal{F}$ of sets is \textit{$P$-free} if it does not contain any copy of $P$. The trace of a family $\mathcal{F}$ on a set $X$ is $\mathcal{F}{|}_X:=\{F\cap X:F\in \mathcal{F}\}$. We introduce the following notions: $\mathcal{F}\subseteq 2^{[n]}$ is $l$-trace $P$-free if for any $l$-subset $L\subseteq [n]$, the family $\mathcal{F}{|}_L$ is $P$-free and $\mathcal{F}$ is trace $P$-free if it is $l$-trace $P$-free for all $l\le n$. As the first instances of these problems we determine the maximum size of trace $B$-free families, where $B$ is the butterfly poset on four elements $a,b,c,d$ with $a,b<c,d$ and determine the asymptotics of the maximum size of $(n-i)$-trace $K_{r,s}$-free families for $i=1,2$. We also propose a generalization of the main conjecture of the area of forbidden subposet problems.