Vertex degrees in grid graphs associated with 213-avoiding permutations
Open Journal of Mathematical Sciences · 17.06.2026 · 10 · 776-789
DOI: 10.30538/oms2026.0316 ↗Kurz gefasst
Fachartikel in der Zeitschrift Open Journal of Mathematical Sciences, online erschienen am 17.06.2026. Verfasst von Nelson Berrocal Huamaní.
Abstract (Originalsprache)
Given a permutation \(\pi\) of size \(n\), we consider the associated grid graph \(G_{\pi}\) whose \(i\)th column has height \(\pi_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 \(\pi\) ranges over the Catalan avoidance class \(\mathrm{Av}_n(213)\) (and, by reversal, also over \(\mathrm{Av}_n(312)\)). We obtain explicit closed formulas for two accumulated quantities over \(\mathrm{Av}_n(213)\): the total number of horizontal edges and, for each \(r\in\{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 \(\mathrm{Av}_n(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.
Zitieren
APA
Huamaní, N. B. (2026). Vertex degrees in grid graphs associated with 213-avoiding permutations. Open Journal of Mathematical Sciences, 10, 776-789. https://doi.org/10.30538/oms2026.0316
Vancouver
Huamaní NB. Vertex degrees in grid graphs associated with 213-avoiding permutations. Open Journal of Mathematical Sciences. 2026;10:776-789. doi:10.30538/oms2026.0316
BibTeX
@article{Huaman2026,
author = {Huamaní, Nelson Berrocal},
title = {Vertex degrees in grid graphs associated with 213-avoiding permutations},
journal = {Open Journal of Mathematical Sciences},
year = {2026},
volume = {10},
pages = {776--789},
doi = {10.30538/oms2026.0316}
}
EUVIMED