The two operations, deletion and contraction of an edge, on multigraphs directly lead to the Tutte polynomial which satisfies a universal problem. As observed by Brylawski (1972) in terms of order relations, these operations may be interpreted as a particular instance of a general theory which involves universal invariants like the Tutte polynomial and a universal group, called the Tutte-Grothendieck group. In this contribution, Brylawski’s theory is extended in two ways: first of all, the order relation is replaced by a string rewriting system, and secondly, commutativity by partial commutations (that permits a kind of interpolation between noncommutativity and full commutativity). This allows us to clarify the relations between the semigroup subject to rewriting and the Tutte-Grothendieck group: the latter is actually the Grothendieck group completion of the former, up to the free adjunction of a unit (this was not even mentioned by Brylawski), and normal forms may be seen as universal invariants. Moreover we prove that such universal constructions are also possible in case of a nonconvergent rewriting system, outside the scope of Brylawski’s work. 1. Introduction In his paper [1], Tutte took advantage of two natural operations on (finite multi) graphs (actually on isomorphism classes of multigraphs), deletion and contraction of an edge, in order to introduce the ring and a polynomial in two commuting variables , also known by Whitney [2], unique up to isomorphism since solutions of a universal problem. This polynomial, since called the Tutte polynomial, is a graph invariant in at least two different meanings: first of all, it is defined on isomorphism classes, rather than on actual graphs, in such a way that two graphs with distinct Tutte polynomials are not isomorphic (a well-known functorial point of view), and, secondly, it is invariant with respect to a graph decomposition. Indeed, let be a graph, and let be an edge of , which is not a loop (an edge with the same vertex as source and target) nor a bridge (an edge that connects two connected components of a graph). The edge contraction of is the graph obtained by identifying the vertices source and target of , and removing the edge . We write for the graph where the edge is merely removed; this operation is the edge deletion. Let us consider the graph (well-defined as isomorphic classes) which can be interpreted as a decomposition of . Then, the Tutte polynomial is invariant with respect to this decomposition in the sense that . Moreover this decomposition eventually terminates with graphs with
References
[1]
W. T. Tutte, “A ring in graph theory,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 43, pp. 26–40, 1947.
[2]
H. Whitney, “The coloring of graphs,” The Annals of Mathematics, vol. 33, no. 4, pp. 688–718, 1933.
[3]
T. H. Brylawski, “The tutte-grothendieck ring,” Algebra Universalis, vol. 2, no. 1, pp. 375–388, 1972.
[4]
S. Mac Lane, Categories for the Working Mathematician, vol. 5 of Graduate Texts in Mathematics, Springer, 1971.
[5]
N. Bourbaki, Elements of Mathematics, Algebra, chapters 1–3, Springer, 1998.
[6]
N. E. Wegge-Olsen, K-Theory and C？-Algebras, Oxford Science, 1993.
[7]
P. May and R. Anno, K-Theory, University of Chicago, REU, 2009.
[8]
P. Cartier and D. Foata, Problèmes Combinatoires de Commutation et Réarrangements, vol. 85 of Lecture Notes in Mathematics, Springer, 1969.
[9]
G. X. Viennot, “Heaps of pieces I: basic definitions and combinatorial lemmas,” in Combinatoire énumérative, G. Labelle, et al., Ed., vol. 1234 of Lecture Notes in Mathematics, pp. 321–350, Montreal, Canada, 1985.
[10]
G. H. E. Duchamp and D. Krob, “Partially commutative formal power series,” in Proceedings of the LITP Spring School on Theoretical Computer Science on Semantics of Systems of Concurrent Processes, pp. 256–276, 1990.
[11]
A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, vol. 1, American Mathematical Society, 1961.
[12]
C. Duboc, Commutations dans les mono？des libres : un cadre théorique pour l’étude du parallélisme [Thèse de doctorat], Université de Rouen, 1986.
[13]
F. Baader and T. Nipkow, Term Rewriting and All That, Cambridge University Press, 1999.
[14]
R. V. Book and F. Otto, String-Rewriting Systems, Springer, 1993.
[15]
V. Diekert, Combinatorics on Traces, vol. 454 of Lecture Notes in Computer Science, Springer, 1990.
[16]
R. P. Stanley, “A Brylawski decomposition for finite ordered sets,” Discrete Mathematics, vol. 4, no. 1, pp. 77–82, 1973.
[17]
G. M. Bergman, “The diamond lemma for ring theory,” Advances in Mathematics, vol. 29, no. 2, pp. 178–218, 1978.
[18]
C. Kassel, Quantum Groups, vol. 155 of Graduate Texts in Mathematics, Springer, 1995.
[19]
N. Bourbaki, Elements of Mathematics, Lie Groups and Lie Algbras, chapters 1–3, Springer.
[20]
G. Birhkhoff, “Representability of Lie algebras and Lie groups by matrices,” The Annals of Mathematics, vol. 38, pp. 526–532, 1937.
[21]
H. Poincaré, “Sur les groupes continus,” Transactions of the Cambridge Philosophical Society, vol. 18, pp. 220–255, 1900.
[22]
E. Witt, “Treue darstellung liescher ringe,” Journal für die Reine und Angewandte Mathematik, vol. 117, pp. 152–160, 1937.
[23]
E. A. Bender and J. R. Goldman, “Enumerative uses of generating functions,” Indiana University Mathematics Journal, vol. 20, pp. 753–765, 1971.
[24]
C. Reutenauer, Free Lie Algebras, Oxford University Press, 1993.
[25]
M. P. Schützenberger, “Pour le mono？de plaxique. Mathématiques,” Informatique et Sciences Humaines, vol. 140, pp. 5–10, 1997.
