Vertex degrees in grid graphs associated with 213-avoiding permutations

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 Av_n (213) (and, by reversal, also over Av_n (312)). We obtain explicit closed formulas for two accumulated quantities over Av_n (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 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.