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

DOI10.1137/15M1054535zbMATH Open1366.05049arXiv1601.01780MaRDI QIDQ5275437FDOQ5275437

Authors: P.-L. Giscard, Paul Rochet 

Publication date: 14 July 2017

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Determinants and Möbius functions in trace monoids
• Combinatorial problems of commutation and rearrangements
• Title not available (Why is that?)
• Quivers, words and fundamentals
• Representations of quivers.
• Zeta functions of graphs. A stroll through the garden
• Self-Avoiding Paths and the Adjacency Matrix of a Graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the average parallelism in trace monoids.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Almost all trees are co-immanantal
• Evaluating matrix functions by resummations on graphs: the method of path-sums

Cited In (11)

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

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)