Algebraic combinatorics on trace monoids: extending number theory to walks on graphs

Abstract

Partially commutative monoids provide a powerful tool to study graphs, viewingwalks as words whose letters, the edges of the graph, obey a specific commutation rule. A particularclass of traces emerges from this framework, the hikes, whose alphabet is the set of simple cycleson the graph. We show that hikes characterize undirected graphs uniquely, up to isomorphism, andsatisfy remarkable algebraic properties such as the existence and uniqueness of a prime factorization.Because of this, the set of hikes partially ordered by divisibility hosts a plethora of relations in directcorrespondence with those found in number theory. Some applications of these results are presented,including a permanantal extension to MacMahon's master theorem and a derivation of the Ihara zetafunction.

References in corpus (2)

• A Graded Möbius transform and its harmonic interpretation
• Relations between connected and self-avoiding walks in a digraph

Cited by in corpus (10)

• BPS operators in $\mathcal{N}=4$ $SO(N)$ super Yang-Mills theory: plethysms, dominoes and words
• A Centrality Measure for Cycles and Subgraphs II
• Cycle-centrality in complex networks
• Enumerating simple paths from connected induced subgraphs
• Evaluating balance on social networks from their simple cycles
• Counting walks by their last erased self-avoiding polygons using sieves
• An Hopf algebra for counting simple cycles
• Realizable cycle structures in digraphs
• A co-preLie structure from chronological loop erasure in graph walks
• $X$-Ramanujan Graphs