Combinatorial Comparison of Trace Monoids via Their Dependence Graph Symmetries
Ioannis Michos, Constantinos Kourouzides · 2025
We ask whether there exist non-isomorphic trace monoids over a fixed alphabet that have the same average parallelism. This question is related to the bivariate generating series F which counts traces by their height and length; trace monoids with the same F also possess the same average parallelism. The series F is known to be rational and has been calculated efficiently via the symmetries of the dependence graph, when the latter is connected. We investigate the existence of non-isomorphic dependence graphs (over a common fixed alphabet) with the same series F. Using fractional graph isomorphisms and certain equitable partitions of the Cartier-Foata clique automaton, we prove two classification results. First, we show that all 2-regular independence graphs of the same order share the same generating series F if and only if they have the same number of triangular connected components. Secondly, for any d≥2, all triangle-free d-regular independence graphs of the same order—except for the complete bipartite graph Kd,d—share this property. The smallest instance of this result for d=3, is the pair consisting of the cube graph Q3 and the Wagner graph M8, both on eight vertices.