Snake Graphs Arising from Groves with an Application in Coding Theory

Abstract

Snake graphs are connected planar graphs consisting of a finite sequence of adjacent tiles (squares) $T_1, T_2, \ldots,T_n$. In this case, for $1 \leq j \leq n-1$ , two consecutive tiles $T_j$ and $T_{j+1}$ share exactly one edge, either the edge at the east (west) of $T_j$ ($T_{j+1}$) or the edge at the north (south) of $T_j$ ($T_{j+1}$). Finding the number of perfect matchings associated with a given snake graph is one of the most remarkable problems regarding these graphs. It is worth noting that such a number of perfect matchings allows a bijection between the set of snake graphs and the positive continued fractions. Furthermore, perfect matchings of snake graphs have also been used to find closed formulas for cluster variables of some cluster algebras and solutions of the Markov equation, which is a well-known Diophantine equation. Recent results prove that snake graphs give rise to some string modules over some path algebras, connecting snake graph research with the theory of representation of algebras. This paper uses this interaction to define Brauer configuration algebras induced by schemes associated with some multisets called polygons. Such schemes are named Brauer configurations. In this work, polygons are given by some admissible words, which, after appropriate transformations, permit us to define sets of binary trees called groves. Admissible words generate codes whose energy values are given by snake graphs. Such energy values can be estimated by using Catalan numbers. We include in this paper Python routines to compute admissible words (i.e., codewords), energy values of the generated codes, Catalan numbers and dimensions of the obtained Brauer configuration algebras.

Publication
Computation, 10(7), Art. 124. doi:10.3390/computation10070124

Related