Vertex degrees in grid graphs associated with 213-avoiding permutations
N. B. Huamaní · 2026
Read Vertex degrees in grid graphs associated with 213-avoiding permutations by N. B. Huamaní (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18173.txt.
Introduction
N. B. Huamaní studies vertex degrees in grid graphs built from permutations that avoid the pattern 213. His 2026 preprint builds the graph column by column, with each column's height set by the permutation entry. Vertical edges join levels inside a column, and horizontal edges join equal levels in neighboring columns. The paper works out how the degrees of the vertices behave in this family.
Catalog record
| CREATOR | N. B. Huamaní |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-18173
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Vertex degrees in grid graphs associated with 213-avoiding permutations N. B. Huamaní Abstract Given a permutation of size n n , we consider its associated grid graph whose i i th column has height equal to the i i th entry, with vertical edges between consecutive levels and horizontal edges between equal levels in adjacent columns. We study global degree statistics of these graphs when the permutation is chosen from the Catalan avoidance class Av n ( 213 ) \mathrm{Av}_{n}(213) (and, by reversal, also from Av n ( 312 ) \mathrm{Av}_{n}(312) ). We first obtain an explicit closed form for the total number of horizontal edges summed over all permutations in Av n ( 213 ) \mathrm{Av}_{n}(213) . We then determine, for each degree r ∈ { 1 , 2 , 3 , 4 } r\in\{1,2,3,4\} , the total number of degree- r r vertices accumulated over the same class, yielding closed expressions in terms of central binomial coefficients and powers of four. The proofs rely on the Catalan decomposition induced by the position of the minimum entry, which leads to gluing identities and algebraic functional equations for ordinary generating functions, completed using global vertex and degree-sum identities. As a consequence, we derive asymptotic degree proportions for a uniform random permutation in Av n ( 213 ) \mathrm{Av}_{n}(213) : the distribution concentrates and the proportion of degree- 4 4 vertices tends to 1 1 , with a deficit of order n − 1 / 2 n^{-1/2} . † † dmtcs-publicationdata: Volume vol. 25:3 special issue for main purpose (2026), #1, doi:10.46298/dmtcs.10472 1 Introduction We study global degree statistics in the grid graphs associated with permutations, restricting the underlying permutation to a Catalan avoidance class. Let n\in\mathbb{N} and [n]=\{1,2,\dots,n\} . Let S_{n} denote the set of all permutations of [n] , that is, all words \pi=\pi_{1}\pi_{2}\cdots\pi_{n} containing each element of [n] exactly once. Following 1 , to each \pi\in S_{n} we associate a grid graph G_{\pi} with n columns: column i has height \pi_{i} ; we place vertical edges between consecutive levels within each column and horizontal edges between equal levels in adjacent columns. For n\geq 2 , every vertex of G_{\pi} has degree in \{1,2,3,4\} ( 1 ) . Two global quantities are immediate from the definition: the total number of vertices satisfies |V(G_{\pi})|=\sum_{i=1}^{n}\pi_{i}=\binom{n+1}{2} (independent of \pi ), and the total number of vertical edges is |E_{\rm vert}(G_{\pi})|=\sum_{i=1}^{n}(\pi_{i}-1)=\binom{n}{2} . In contrast, the horizontal edges depend on \pi and are given by the statistic H(\pi)=\sum_{t=1}^{n-1}\min\{\pi_{t},\pi_{t+1}\}. In the unrestricted case (averaging over S_{n} ), 1 obtain closed formulas for the total number of horizontal edges and for the global vertex counts by degree, together with limiting proportions. Moreover, in the final section of 1 they propose extending this program to avoidance classes \mathrm{Av}_{n}(\tau) , where \tau is a pattern of length 3 . In this paper we treat completely the Catalan class \mathrm{Av}_{n}(213) . Unlike the unrestricted case, pattern avoidance imposes a rigid block structure: if the entry 1 occurs in position k , then every value to the left of 1 is larger than every value to the right, forcing a Catalan gluing by lengths. This rigidity is reflected in the column profile of G_{\pi} . Figure 1 compares two examples in \mathrm{Av}_{4}(213) with a permutation containing the pattern 213 . Figure file Figure213.pdf not found. (This placeholder allows the source to compile without the figure.) Figure 1: Grid graphs G_{\pi} for n=4 : (a) \pi=4132 , (b) \pi=3412 (both in \mathrm{Av}_{4}(213) ), and (c) \pi=2134 , which contains the pattern 213 . Our main results are closed formulas for global totals as \pi ranges over \mathrm{Av}_{n}(213) . First, for the total number of horizontal edges H_{n}=\sum_{\pi\in\mathrm{Av}_{n}(213)}H(\pi) we obtain an explicit expression in terms of central binomial coefficients and powers of 4 . Second, for each r\in\{1,2,3,4\} we derive a closed form for Q_{r}(n):=\sum_{\pi\in\mathrm{Av}_{n}(213)}\#\{v\in V(G_{\pi}):\deg(v)=r\}. As a consequence, the proportion of degree- 4 vertices tends to 1 as n\to\infty , with a leading correction of order n^{-1/2} ; this contrasts with the unrestricted case ( 1 ) , where the limiting proportion for degree 4 equals 1/2 . Moreover, by reversal, all results transfer automatically to \mathrm{Av}_{n}(312) . Our strategy is entirely Catalan: we start from the decomposition induced by the position of the minimum 1 , translate local contributions into gluing identities and functional equations for ordinary generating functions algebraic over \mathbb{Q}(x,\sqrt{1-4x}) , and close the system using global identities (total number of vertices and sum of degrees). The paper is organized as follows: in Section 2 we fix definitions and local degree criteria; in Section 3 we establish the decomposition by the position of 1 ; in Section 4 we close H_{n} ; in Section 5 we introduce the global degree totals and the identities that close the system; in Section 6 we determine Q_{1}(n) ; in Section 7 we determine Q_{4}(n) ; in Section 8 we package the closed forms for Q_{1}(n),\dots,Q_{4}(n) ; in Section 9 we extract limiting proportions and leading corrections and compare with ( 1 ) ; and finally we conclude with a brief discussion of remaining cases and further directions. 2 Preliminaries We collect the basic definitions and notation: the grid graph G_{\pi} , local degree-by-level criteria, Catalan enumeration for \mathrm{Av}_{n}(213) and its generating function, and the reversal symmetry used to transfer results to \mathrm{Av}_{n}(312) . 2.1 Grid graphs Definition 2.1 . Let \pi=\pi_{1}\cdots\pi_{n}\in S_{n} . The grid graph G_{\pi} has vertex set V(G_{\pi})=\{(i,j):1\leq i\leq n,\ 1\leq j\leq\pi_{i}\}. Two vertices (i,j) and (i^{\prime},j^{\prime}) are adjacent if: (i) i=i^{\prime} and |j-j^{\prime}|=1 (a vertical edge), or (ii) |i-i^{\prime}|=1 and j=j^{\prime} (a horizontal edge), provided both vertices exist. For n\geq 2 , every vertex of G_{\pi} has degree in \{1,2,3,4\} ( 1 ) . We write \deg(v) for the degree of v , and E_{\rm vert}(G_{\pi}) , E_{\rm hor}(G_{\pi}) for the sets of vertical and horizontal edges. 2.2 Local degree criteria by level Lemma 2.2 . Let \pi\in S_{n} and consider a column i of height b=\pi_{i} . (i) If 2\leq i\leq n-1 (internal column) and a=\pi_{i-1} , c=\pi_{i+1} , then for 1\leq s\leq b \deg(i,s)=\mathbf{1}_{\{s>1\}}+\mathbf{1}_{\{s<b\}}+\mathbf{1}_{\{s\leq a\}}+\mathbf{1}_{\{s\leq c\}}. (1) (ii) If i=1 (left external column) and b=\pi_{1} , c=\pi_{2} , then for 1\leq s\leq b \deg(1,s)=\mathbf{1}_{\{s>1\}}+\mathbf{1}_{\{s<b\}}+\mathbf{1}_{\{s\leq c\}}. Similarly, if i=n and a=\pi_{n-1} , then \deg(n,s)=\mathbf{1}_{\{s>1\}}+\mathbf{1}_{\{s<b\}}+\mathbf{1}_{\{s\leq a\}}. Proof. In any column, vertical neighbors exist exactly when s>1 (a lower neighbor) and s<b (an upper neighbor). In an internal column there are two possible horizontal neighbors: to the left if s\leq a and to the right if s\leq c . In an external column there is only one possible horizontal neighbor. Summing these contributions yields the stated formulas. ∎ Corollary 2.3 . In an internal column with triple (a,b,c) , the number of degree- 4 vertices in the middle column is \max\{0,\min(a,c,b-1)-1\}. Proof. By ( 1 ), a level s has degree 4 if and only if 2\leq s\leq b-1 and also s\leq a and s\leq c . This is equivalent to 2\leq s\leq\min(a,c,b-1) , and the count is immediate. ∎ Corollary 2.4 . Let 2\leq i\leq n-1 . The top vertex (i,\pi_{i}) has degree 1 if and only if \pi_{i}\geq 2 and \pi_{i}>\max\{\pi_{i-1},\pi_{i+1}\} .