Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.12641 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918446017544192 |
|---|---|
| author | Ciceksiz, R. Altar Falgas-Ravry, Victor Lato, Sabrina Sharifzadeh, Maryam |
| author_facet | Ciceksiz, R. Altar Falgas-Ravry, Victor Lato, Sabrina Sharifzadeh, Maryam |
| contents | Set $[n]=\{1, 2, \ldots , n\}$. The hypergrid $[t]^n$ is the collection of functions $f: \ [n]\rightarrow [t]$. We equip it with the natural partial order by letting $f\leq g$ whenever $f(x)\leq g(x)$ holds for all $x\in [n]$. Given a poset $P$ which can be embedded as an induced subposet of $[t]^n$, the induced poset saturation function $\mathrm{sat}^{\star}([t]^n, P)$ denotes the minimum size of a subset of $[t]^n$ that is both induced $P$-free and induced $P$-saturated.
We show that for all $t\geq 2$, $\mathrm{sat}^{\star}([t]^n, P)$ satisfies a dichotomy: for every poset $P$, either there exists a constant $C_P$ such that $\mathrm{sat}^{\star}([t]^n, P)=C_P$ for all $n$ sufficiently large, or $\mathrm{sat}^{\star}([t]^n, P)=Ω(\sqrt{n})$. We also show chains fall in the former part of the dichotomy, while posets with the unique twin cover property fall in the latter part. These contributions generalize a number of results obtained by various authors in the hypercube ($t=2$) setting; the transition to the hypergrid setting provides novel challenges, however, and requires some new ideas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_12641 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Induced poset saturation in the hypergrid Ciceksiz, R. Altar Falgas-Ravry, Victor Lato, Sabrina Sharifzadeh, Maryam Combinatorics 05D05 Set $[n]=\{1, 2, \ldots , n\}$. The hypergrid $[t]^n$ is the collection of functions $f: \ [n]\rightarrow [t]$. We equip it with the natural partial order by letting $f\leq g$ whenever $f(x)\leq g(x)$ holds for all $x\in [n]$. Given a poset $P$ which can be embedded as an induced subposet of $[t]^n$, the induced poset saturation function $\mathrm{sat}^{\star}([t]^n, P)$ denotes the minimum size of a subset of $[t]^n$ that is both induced $P$-free and induced $P$-saturated. We show that for all $t\geq 2$, $\mathrm{sat}^{\star}([t]^n, P)$ satisfies a dichotomy: for every poset $P$, either there exists a constant $C_P$ such that $\mathrm{sat}^{\star}([t]^n, P)=C_P$ for all $n$ sufficiently large, or $\mathrm{sat}^{\star}([t]^n, P)=Ω(\sqrt{n})$. We also show chains fall in the former part of the dichotomy, while posets with the unique twin cover property fall in the latter part. These contributions generalize a number of results obtained by various authors in the hypercube ($t=2$) setting; the transition to the hypergrid setting provides novel challenges, however, and requires some new ideas. |
| title | Induced poset saturation in the hypergrid |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2604.12641 |