Maximal anti-Ramsey problems for posets
Abstract
We study the forbidden poset analog of the maximal anti-Ramsey problem introduced for graphs by Burr, Erd\H os, Graham, and Sós. For integers m≤ 2n and poset P=(P,⪯), we introduce arm(n,m,P) (and ar*m(n,m,P)) to denote the minimum integer k such that there exists a family ℱ⊆ 2[n] with |ℱ|=m and a coloring ℱ→ [k] with all weak (strong) copies of P being rainbow. As long as there exist P-free families of size m, these parameters equal 1. It is known that the largest size La(n,P) (La*(n,P)) of weak (strong) P-free families has order of magnitude Θ(binomn⌊ n/2⌋) unless P is the antichain Ak on k elements. In this paper we study arm(n,m,P) and ar*m(n,m,P) in two regimes of m. We determine the asymptotics of these parameters for all posets P when m=2n. We also consider the case m=Θ(binomn⌊ n/2⌋). It is shown that for any connected poset P and integer k, there exist integers mP,k and m*P,k such that to color the middle k layers of the Boolean lattice with all weak or strong copies of P being rainbow, one needs Θ(nmP,k) or Θ(nm*P,k) colors. For tree posets T, one has mT,k=m*T,k. We conjecture that for any tree poset T, and positive real ε, arm(n,m,T),ar*m(n,m,T)=Ω(nmT,k) holds provided m≥ (k−1+ε)binomn⌊ n/2⌋. We prove our conjecture on arm(n,m,T) for an infinite class of tree posets.
Related
- Fence Posets, Good Gradings and Frobenius Maximal Parabolics
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- Ramsey properties of maximal (outer)planar graphs
- On the lower- and upper bounds of three-colored anti-Ramsey numbers
- Anti-Ramsey Number of Intersecting Odd Cycles
BibTeX
@misc{li2026maximal,
title = {{Maximal anti-Ramsey problems for posets}},
author = {Binlong Li and Balázs Patkós and Changxin Wang},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30354},
eprint = {2608.30354},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30354},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Maximal anti-Ramsey problems for posets
AU - Binlong Li
AU - Balázs Patkós
AU - Changxin Wang
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30354
UR - https://arxiv.org/abs/2608.30354
AB - We study the forbidden poset analog of the maximal anti-Ramsey problem introduced for graphs by Burr, Erd\H os, Graham, and Sós. For integers m≤ 2^n and poset P=(P,⪯), we introduce ar_m(n,m,P) (and ar^*_m(n,m,P)) to denote the minimum integer k such that there exists a family ℱ⊆ 2^[n] with |ℱ|=m and a coloring ℱ→ [k] with all weak (strong) copies of P being rainbow. As long as there exist P-free families of size m, these parameters equal 1. It is known that the largest size La(n,P) (La^*(n,P)) of weak (strong) P-free families has order of magnitude Θ(binomn⌊ n/2⌋) unless P is the antichain A_k on k elements. In this paper we study ar_m(n,m,P) and ar^*_m(n,m,P) in two regimes of m. We determine the asymptotics of these parameters for all posets P when m=2^n. We also consider the case m=Θ(binomn⌊ n/2⌋). It is shown that for any connected poset P and integer k, there exist integers m_P,k and m^*_P,k such that to color the middle k layers of the Boolean lattice with all weak or strong copies of P being rainbow, one needs Θ(n^m_P,k) or Θ(n^m^*_P,k) colors. For tree posets T, one has m_T,k=m^*_T,k. We conjecture that for any tree poset T, and positive real ε, ar_m(n,m,T),ar^*_m(n,m,T)=Ω(n^m_T,k) holds provided m≥ (k−1+ε)binomn⌊ n/2⌋. We prove our conjecture on ar_m(n,m,T) for an infinite class of tree posets.
ER -