2025/11/08 by Reza Rastegar, Rastegar, Reza
Mathematics · #Advanced Combinatorial Mathematics #Markov Chains and Monte Carlo Methods #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2511.06118
(Work in progress) Marcus and Tardos \citeMarcusTardos2004 proved the Stanley--Wilf conjecture by reducing pattern avoidance to an extremal problem on 0--1 matrices. We give a parallel proof for classical permutation patterns that stays entirely in the ``grow from the right'' world of enumerative combinatorics. A v-avoiding permutation is built by right insertion; at each step we keep a pruned family of locations of (k-1)-partial occurrences of v (the frontier), each carrying its forbidden rank interval. The insertion step then induces a nonnegative transfer operator on a doubly weighted ℓ^∞ space. A quadratic penalty in the length makes this operator bounded, and a Neumann-series argument on a natural separable predual yields analyticity of the growth series, hence finite exponential growth for \Av(v). The formulation is completely internal -- we never pass to 0--1 matrices -- and it cleanly separates the pattern-dependent combinatorics of the frontier from a purely operator-theoretic core. In particular, we obtain an abstract ``right-insertion/transfer-operator'' theorem: any system whose frontier grows at most linearly and whose transfer operator satisfies a uniform quadratic length bound has an analytic growth series.