Induced poset saturation in the hypergrid

Abstract

Set $[n]=\{1,2,\dots ,n\}$. The hypergrid $[t{]}^n$ is the collection of functions $f:[n]\to [t]$. We equip it with the natural partial order by letting $f\le g$ whenever $f(x)\le 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\ge 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)=\hat{I}\text{c◯}(\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.

16 pages