{
  "id": "1706.01212",
  "version": "v1",
  "published": "2017-06-05T06:46:40.000Z",
  "updated": "2017-06-05T06:46:40.000Z",
  "title": "Forbidden subposet problems for traces of set families",
  "authors": [
    "Dániel Gerbner",
    "Balázs Patkós",
    "Máté Vizer"
  ],
  "categories": [
    "math.CO"
  ],
  "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\\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 $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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-05T06:46:40.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "forbidden subposet problems",
      "set families",
      "free families",
      "bridges forbidden subposet",
      "forbidden subconfiguration problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}