The Tutte-Grothendieck Group of an Alphabetic Rewriting System. (13th January 2013)

• Record Type: Journal Article
• Authors: Poinsot, Laurent
• Other Names: Godbole A. P. Academic Editor.; Jou M.-J. Academic Editor.; Taeri B. Academic Editor.
• Is Part Of: ISRN combinatorics. Volume 2013(2013)
• Publication Date: 2013-01-13
• Subjects: Combinatorial analysis -- Periodicals; Combinatorial analysis; Electronic journals; Periodicals; 511.6
• DOI: 10.1155/2013/574578
• Languages: English
• ISSNs: 2090-8911

Abstract

Abstract : 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.