Crab Research
返回结果列表
组合数学

相邻差有界的 132 避免排列:严格增长与下降阈值

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

Alex Chengyu Li

工作论文 · Zenodo首次公开

研究概述

若一个排列中不存在三个元素按 132 的相对大小次序出现,就称它避免 132。把相邻数值的绝对差限制为至多 m,所得排列族的指数增长率随 m 严格增加;这一结果在 Mayama 和 Akita 的计数理论基础上,补齐了 Nadler 猜想 2 中剩余的断言。下降是指一个元素大于紧随其后的元素。给每个下降赋予权重后,会出现增长率等于一的区域,以及两种不同尺度的阈值。论文在同一篇中证明了带权增长判据及其极限增长率。

原文摘要(英文)

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.

公开摘要来源

原始公开问题

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

数学审核

内部定稿

稿件已完成内部审核,当前公开版本尚未完成完整形式化。

审核标准
返回结果列表
返回 数学