Strict Growth and Descent Thresholds for Bounded-Gap 132-Avoiders
Overview
A permutation avoids 132 when it has no three entries in that relative order. Restricting absolute differences of adjacent values to at most m gives a family whose exponential growth strictly increases with m, completing the remaining assertion of Nadler's Conjecture 2 after Mayama and Akita's enumeration. Weighting each descent, where an entry exceeds its successor, reveals a growth-one region and two different threshold scales. The paper proves the weighted growth criterion and limiting rate in the same article.
Original abstract (English)
We prove that the exponential growth constants of 132-avoiding permutations with adjacent value differences at most m are strictly increasing in m. This establishes the remaining strictness assertion in Nadler's growth conjecture, following the finite-state enumeration of Mayama and Akita. The comparison comes from shifting both endpoint thresholds in their state system. We extend it to enumeration with a positive weight for each descent. In the weighted model, there is a strictly decreasing sequence of positive thresholds of order m to the power minus two, below which the exponential growth is one. Above the appropriate threshold, each increase of the gap bound strictly increases growth. For every fixed positive descent weight t, the growth constants converge to (1 + sqrt(t)) squared. The two nontrivial state components have separated descent thresholds, of orders m to the power minus two and (log(m)/m) squared. The results combine a coefficientwise component embedding with elimination of the acyclic append transitions.
Original public questions
Nathaniel Nadler: On 132-Avoiding Permutations with an Adjacency Constraint — Conjecture 2, Section 5.2, arXiv v1; the remaining consecutive strict-growth assertion
Teruki Mayama and Dai Akita: Finite-state enumeration of adjacency-constrained 132-avoiding permutations — Theorems 4.12 and 4.14 for the prior growth results; Section 5 P4 for the descent refinement
Mathematical review
The manuscript has completed internal review. Complete formalization is not yet established for this public version.
Review standard