Pattern-Avoidance Inequalities on Digitally Convex Shapes

Definitions and mathematical statement

For the side parameter $n$ appearing in the supplied statement, write $[n]=\{1,\ldots,n\}$, and let $S_n$ be the set of bijections $\sigma:[n]\to[n]$. Let $\lambda\subseteq{\mathbb{Z}}^2$ be a digitally convex shape of side $n$, in the intended sense of the source. Define \[ S_\lambda=\{\sigma\in S_n:(i,\sigma(i))\in\lambda\text{ for every }i\in[n]\}. \] For $\sigma\in S_\lambda$, define the set of forbidden increasing triples by \[ T_\lambda(\sigma)=\left\{(i,j,k)\in[n]^3: \begin{gathered} i<j<k,\qquad \sigma(i)<\sigma(j)<\sigma(k),\\ (i,\sigma(k))\in\lambda,\qquad (k,\sigma(i))\in\lambda \end{gathered} \right\}. \] Set \[ A_\lambda=\left|\{\sigma\in S_\lambda:T_\lambda(\sigma)=\varnothing\}\right|. \] A red-and-blue coloring of $\sigma$ is a function $c:[n]\to\{\mathrm{red},\mathrm{blue}\}$, assigning a color to each graph point $(i,\sigma(i))$. Call $c$ admissible if, for every $i,j\in[n]$ with $i<j$ and $\sigma(i)<\sigma(j)$, both implications \[ \begin{aligned} c(i)=c(j)=\mathrm{red}&\ \Longrightarrow\ (j,\sigma(i))\notin\lambda,\\ c(i)=c(j)=\mathrm{blue}&\ \Longrightarrow\ (i,\sigma(j))\notin\lambda \end{aligned} \] hold. Let $C_\lambda(\sigma)$ be the set of admissible colorings, and put \[ B_\lambda=\sum_{\sigma\in S_\lambda}|C_\lambda(\sigma)|. \] Thus distinct admissible colorings of the same permutation are counted separately.

Conjecture as supplied. For every digitally convex shape $\lambda\subseteq{\mathbb{Z}}^2$ of side $n$, \[ B_\lambda\geq A_\lambda. \] Unresolved qualification. The supplied record does not define "digitally convex shape" or "side $n$." In particular, it does not specify the permitted side parameters or the coordinate placement and boundary conventions for such shapes. The definitions of the two counts above are explicit once $n$ and $\lambda$ are fixed, but the universal domain of the conjecture remains conditional on the intended source definitions.

Short English statement

For each intended digitally convex shape, compare the number of permutations avoiding the specified increasing triples with the number of red-and-blue colored permutations avoiding the two specified monochromatic increasing pairs. The conjecture says that the colored count is at least the uncolored count. The supplied record leaves the class of digitally convex shapes and its side convention undefined.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003821$, title: Pattern-Avoidance Inequalities on Digitally Convex Shapes; exact source problem code: catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2018.
• Supplied source citation: Enumerative Combinatorics (2019), Oberwolfach Reports, pp. 1381--1464, DOI 10.4171/owr/2018/23: https://doi.org/10.4171/owr/2018/23. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The relationship between the citation's 2019 designation and the record's 2018 proposal year is not explained.
• Supplied literature source, labeled "original OWR report": https://doi.org/10.4171/owr/2018/23. The literature assessment was checked on 2026-08-21, according to the supplied record. This is supplied dated curation, not an independently verified assessment. It labels the conjecture open and states that related pattern-avoidance and digital-convexity results do not establish the inequality for all shapes. The background explicitly calls this dated literature triage and requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that the official Oberwolfach report was checked directly, with definitions restored and source-dependent wording removed. These are supplied verification claims; no independent source inspection or mathematical verification is asserted here.