Vertex degrees in grid graphs associated with 213-avoiding permutations

Huamaní N.B. · Open Journal of Mathematical Sciences (2026) · DOI: 10.30538/oms2026.0316

Resumen

Given a permutation π of size n, we consider the associated grid graph Gπ whose ith column has height πi, with vertical edges between consecutive levels and horizontal edges between equal levels in adjacent columns. We investigate global degree statistics of these graphs when π ranges over the Catalan avoidance class Avn (213) (and, by reversal, also over Avn (312)). We obtain explicit closed formulas for two accumulated quantities over Avn (213): the total number of horizontal edges and, for each r ∈ {1, 2, 3, 4}, the total number of degree-r vertices. The proofs rely on the Catalan decomposition induced by the position of the minimum entry, which leads to gluing recurrences and algebraic ordinary generating functions, and are completed using universal identities for the total number of vertices and the sum of degrees. As an application, we derive asymptotic degree proportions for a uniformly random permutation in Avn (213): the expected proportion of degree-4 vertices, equivalently the global degree-4 proportion over the class, tends to 1, with a deficit of order n−1/2, contrasting with the unrestricted case.

Instituciones: Universidad Nacional de San Cristóbal de Huamanga