EUVIMEDEUVIMED entdecken
Crossref

Vertex degrees in grid graphs associated with 213-avoiding permutations

Nelson Berrocal Huamaní

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í.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →