Rainbow Turán problems for forbidden subposets
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908666410565632 |
|---|---|
| author | Patkós, Balázs |
| author_facet | Patkós, Balázs |
| contents | A family $\mathcal{G}$ of sets is a copy of a poset $(P,\leqslant)$ if $(\mathcal{G},\subseteq)$ is isomorphic to $(P,\leqslant)$. The forbidden subposet problem asks for determining $La^*(n,P)$, the maximum size of a family $\mathcal{F}\subseteq 2^{[n]}$ that does not contain any copy of $P$. We study the rainbow version of this problem: what is the maximum size $La_R^*(n,P)$ of a family $\mathcal{F}=\cup_{i=1}^mA^i$ such that all $A^i$ are antichains and there is no copy of $P$ with all sets coming from distinct $A^i$ or equivalently $\mathcal{F}$ admits a proper coloring (sets $F\subset F'$ must receive different colors) with no rainbow copy of $P$.
A poset $(Q,\leqslant')$ rainbow forces $(P,\leqslant)$ if any proper coloring $c$ of $Q$ ($q\leqslant' q'$ or $q'\leqslant' q$ implies $c(q)\neq c(q')$) admits a rainbow copy of $P$. We establish connection between the $La^*$ and the $La^*_R$ functions via poset rainbow forcing, determine the asymptotics of $La_R^*(n,T)$ for all tree posets and obtain further exact or asymptotic results for antichains and complete bipartite posets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14298 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rainbow Turán problems for forbidden subposets Patkós, Balázs Combinatorics A family $\mathcal{G}$ of sets is a copy of a poset $(P,\leqslant)$ if $(\mathcal{G},\subseteq)$ is isomorphic to $(P,\leqslant)$. The forbidden subposet problem asks for determining $La^*(n,P)$, the maximum size of a family $\mathcal{F}\subseteq 2^{[n]}$ that does not contain any copy of $P$. We study the rainbow version of this problem: what is the maximum size $La_R^*(n,P)$ of a family $\mathcal{F}=\cup_{i=1}^mA^i$ such that all $A^i$ are antichains and there is no copy of $P$ with all sets coming from distinct $A^i$ or equivalently $\mathcal{F}$ admits a proper coloring (sets $F\subset F'$ must receive different colors) with no rainbow copy of $P$. A poset $(Q,\leqslant')$ rainbow forces $(P,\leqslant)$ if any proper coloring $c$ of $Q$ ($q\leqslant' q'$ or $q'\leqslant' q$ implies $c(q)\neq c(q')$) admits a rainbow copy of $P$. We establish connection between the $La^*$ and the $La^*_R$ functions via poset rainbow forcing, determine the asymptotics of $La_R^*(n,T)$ for all tree posets and obtain further exact or asymptotic results for antichains and complete bipartite posets. |
| title | Rainbow Turán problems for forbidden subposets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.14298 |