In this paper, we associate a finite dimensional algebra, called a Brauer graph algebra, to every clean dessin d’enfant by constructing a quiver based on the monodromy of the dessin. We show that ...Galois conjugate dessins d’enfants give rise to derived equivalent Brauer graph algebras and that the stable Auslander-Reiten quiver and the dimension of the Brauer graph algebra are invariant under the induced action of the absolute Galois group.
A classical problem in Distance Geometry, with multiple practical applications (in molecular structure determination, sensor network localization etc.) is to find the possible placements of the ...vertices of a graph with given edge lengths. For minimally rigid graphs, the double-exponential Gr\"obner Bases algorithm with an elimination order can be applied, in theory, but it is impractical even for small instances. By relating the problem to the computation of circuit polynomials in the Cayley-Menger ideal, we recently proposed an algebraic-combinatorial approach and an elimination algorithm for circuit polynomials 23. It is guided by a tree structure whose leaves correspond to complete \(K_4\) graphs and whose nodes perform algebraic resultant operations. In this paper we uncover further combinatorial structure in the Cayley-Menger algebraic matroid that leads to an extension of our algorithm. In particular, we generalize the combinatorial resultant operation of 23 to take advantage of the non-circuit generators and irreducible polynomials in the Cayley-Menger ideal and use them as leaves of the tree guiding the elimination. Our new method has been implemented in Mathematica and allows previously unobtainable calculations to be carried out. In particular, the \(K_{3,3}\)-plus-one circuit polynomial, with over one million terms in 10 variables and whose calculation crashed after several days with the previous method of 23, succeeded now in approx. 30 minutes.
Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid associated to the ...Cayley-Menger ideal for \(n\) points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from \(K_4\) graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Groebner Basis calculation took 5 days and 6 hrs.
In this paper we associate to a dessin d'enfant an associative algebra, called a Brauer configuration algebra. This is an algebra given by quiver and relations induced by the monodromy of the dessin ...d'enfant. We show that the dimension of the Brauer configuration algebra associated to a dessin d'enfant and the dimension of the centre this algebra are invariant under the action of the absolute Galois group. We give some examples of well-known algebras and their dessins d'enfants. Finally we show that the Brauer configuration algebras of a dessin d'enfant and its dual share the same path algebra.
Given a map \(\mathcal M\) on a connected and closed orientable surface, the delta-matroid of \(\mathcal M\) is a combinatorial object associated to \(\mathcal M\) which captures some topological ...information of the embedding. We explore how delta-matroids associated to dessins d'enfants behave under the action of the absolute Galois group. Twists of delta-matroids are considered as well; they correspond to the recently introduced operation of partial duality of maps. Furthermore, we prove that every map has a partial dual defined over its field of moduli. A relationship between dessins, partial duals and tropical curves arising from the cartography groups of dessins is observed as well.
A rigidity circuit (in 2D) is a minimal dependent set in the rigidity matroid, i.e. a minimal graph supporting a non-trivial stress in any generic placement of its vertices in \(\mathbb R^2\). Any ...rigidity circuit on \(n\geq 5\) vertices can be obtained from rigidity circuits on a fewer number of vertices by applying the combinatorial resultant (CR) operation. The inverse operation is called a combinatorial resultant decomposition (CR-decomp). Any rigidity circuit on \(n\geq 5\) vertices can be successively decomposed into smaller circuits, until the complete graphs \(K_4\) are reached. This sequence of CR-decomps has the structure of a rooted binary tree called the combinatorial resultant tree (CR-tree). A CR-tree encodes an elimination strategy for computing circuit polynomials via Sylvester resultants. Different CR-trees lead to elimination strategies that can vary greatly in time and memory consumption. It is an open problem to establish criteria for optimal CR-trees, or at least to characterize those CR-trees that lead to good elimination strategies. In 12 we presented an algorithm for enumerating CR-trees where we give the algorithms for decomposing 3-connected rigidity circuits in polynomial time. In this paper we focus on those circuits that are not 3-connected, which we simply call 2-connected. In order to enumerate CR-decomps of 2-connected circuits \(G\), a brute force exp-time search has to be performed among the subgraphs induced by the subsets of \(V(G)\). This exp-time bottleneck is not present in the 3-connected case. In this paper we will argue that we do not have to account for all possible CR-decomps of 2-connected rigidity circuits to find a good elimination strategy; we only have to account for those CR-decomps that are a 2-split, all of which can be enumerated in polynomial time. We present algorithms and computational evidence in support of this heuristic.
PDF