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

DOI10.1137/15M1054535MaRDI QIDQ5275437zbMATHFDO

Authors P.-L. Giscard, Paul Rochet

Publication date 14 July 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.01780

zbMATH Keywords

digraphIhara zeta functionwalksposetincidence algebraweighted adjacency matrixtrace monoidMacMahon master theorem

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Paths and cycles (05C38) Algebraic combinatorics (05E99) Algebraic aspects of posets (06A11)

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.

Recommendations

• Relations between connected and self-avoiding hikes in labelled complete digraphs
• Graphs and free partially commutative monoids
• Algebraic combinatorics. Walks, trees, tableaux, and more
• scientific article; zbMATH DE number 1296975
• Algebraic Combinatorics

Cites work

• scientific article; zbMATH DE number 4162275 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 568838 (Why is no real title available?)
• scientific article; zbMATH DE number 2133276 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3411062 (Why is no real title available?)
• scientific article; zbMATH DE number 3420754 (Why is no real title available?)
• Almost all trees are co-immanantal
• Combinatorial problems of commutation and rearrangements
• Computing the average parallelism in trace monoids.
• Determinants and Möbius functions in trace monoids
• Evaluating matrix functions by resummations on graphs: the method of path-sums
• Quivers, words and fundamentals
• Representations of quivers.
• Self-Avoiding Paths and the Adjacency Matrix of a Graph
• Zeta functions of graphs. A stroll through the garden

Cited in

(11)

• BPS operators in \( \mathcal{N}=4 \) SO(\(N\)) super Yang-Mills theory: plethysms, dominoes and words
• scientific article; zbMATH DE number 5064471 (Why is no real title available?)
• Relations between connected and self-avoiding hikes in labelled complete digraphs
• A co-preLie structure from chronological loop erasure in graph walks
• Algebraic Combinatorics
• Counting walks by their last erased self-avoiding polygons using sieves
• Traces on diagram algebras I: Free partition quantum groups, random lattice paths and random walks on trees
• A coupling of the spectral measures at a vertex
• A Hopf algebra for counting cycles
• Realizable cycle structures in digraphs
• Walks on graphs and their connections with tensor invariants and centralizer algebras

This page was built for publication: Algebraic combinatorics on trace monoids: extending number theory to walks on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5275437)