Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Renormalization grou ...
Conference paper

Renormalization group-like proof of the universality of the Tutte polynomial for matroids

G. Duchamp (1), N. Hoang-Nghia (1), Thomas Krajewski ORCID (2), A. Tanasa (1) (3)
(1) Laboratoire d'Informatique de Paris-Nord
(2) Centre de Physique Théorique - UMR 7332
(3) Horia Hulubei National Institute of Physics and Nuclear Engineering
Download article
Open on HAL
Imported on
November 20, 2016
Published on
December 31, 2012
Last modified on
April 1, 2025
Volume
DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Proceedings
DOI
10.46298/dmtcs.12821
License
https://about.hal.science/hal-authorisation-v1
Indicators
457
Views
389
Downloads

Renormalization group-like proof of the universality of the Tutte polynomial for matroids

G. Duchamp (1), N. Hoang-Nghia (1), Thomas Krajewski ORCID (2), A. Tanasa (1) (3)
(1) Laboratoire d'Informatique de Paris-Nord
(2) Centre de Physique Théorique - UMR 7332
(3) Horia Hulubei National Institute of Physics and Nuclear Engineering
Abstract
English
In this paper we give a new proof of the universality of the Tutte polynomial for matroids. This proof uses appropriate characters of Hopf algebra of matroids, algebra introduced by Schmitt (1994). We show that these Hopf algebra characters are solutions of some differential equations which are of the same type as the differential equations used to describe the renormalization group flow in quantum field theory. This approach allows us to also prove, in a different way, a matroid Tutte polynomial convolution formula published by Kook, Reiner and Stanton (1999). This FPSAC contribution is an extended abstract.
French
Dans cet article, nous donnons une nouvelle preuve de l’universalité du polynôme de Tutte pour les matroïdes. Cette preuve utilise des caractères appropriés de l’algèbre de Hopf des matroïdes introduite par Schmitt (1994). Nous montrons que ces caractères algèbre de Hopf sont des solutions d'équations différentielles du même type que les équations différentielles utilisées pour décrire le flux du groupe de renormalisation en théorie quantique de champs. Cette approche nous permet aussi de démontrer, d’une manière différente, une formule de convolution du polynôme de Tutte des matroïdes, formule publiée par Kook, Reiner et Stanton (1999). Cette contribution FPSAC est un résumé étendu.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Tutte polynomial for matroids
  • Hopf algebras for matroids
  • Hopf algebra characters
  • matroid recipe theorem
  • Combinatorial Physics
Preview
Loading PDF preview...