Forbidden subposet problems for traces of set families (Q1784275): Difference between revisions

Summary: In this paper we introduce a problem that bridges forbidden subposet and forbidden subconfiguration problems. The sets \(F_1,F_2, \ldots,F_{|P|}\) form a \textit{copy} of a poset \(P\), if there exists a bijection \(i:P\rightarrow \{F_1,F_2, \dots,F_{|P|}\}\) such that for any \(p,p'\in P\) the relation \(p<_P p'\) implies \(i(p)\subsetneq i(p')\). 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 \textit{\(l\)-trace \(P\)-free} if for any \(l\)-subset \(L\subseteq [n]\), the family \(\mathcal{F}|_L\) is \(P\)-free and \(\mathcal{F}\) is \textit{trace \(P\)-free} if it is \(l\)-trace \(P\)-free for all \(l\leq 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.