Crab Research
Return to results
Combinatorics

Strict Growth and Descent Thresholds for Bounded-Gap 132-Avoiders

Alex Chengyu Li

Working Paper · ZenodoFirst public

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.

Public abstract source

Original public questions

Nathaniel Nadler: On 132-Avoiding Permutations with an Adjacency ConstraintConjecture 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 permutationsTheorems 4.12 and 4.14 for the prior growth results; Section 5 P4 for the descent refinement

132-avoiding permutationsNadler Conjecture 2bounded adjacent differencesadjacency-constrained permutationsstrict growth constantsdescent thresholdsMayama and Akita

Mathematical review

Paper Close

The manuscript has completed internal review. Complete formalization is not yet established for this public version.

Review standard
Return to results
Back to Mathematics