
arXiv: 1706.01212
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\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 $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.
Combinatorics of partially ordered sets, QA Mathematics / matematika, Extremal set theory, FOS: Mathematics, trace of a set family, Mathematics - Combinatorics, forbidden subposet problem, butterfly poset, Combinatorics (math.CO)
Combinatorics of partially ordered sets, QA Mathematics / matematika, Extremal set theory, FOS: Mathematics, trace of a set family, Mathematics - Combinatorics, forbidden subposet problem, butterfly poset, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
