The Incidence Hopf Algebra of Graphs
International audience The graph algebra is a commutative, cocommutative, graded, connected incidence Hopf algebra, whose basis elements correspond to finite simple graphs and whose Hopf product and coproduct admit simple combinatorial descriptions. We give a new formula for the antipode in the grap...
Main Authors: | , |
---|---|
Other Authors: | , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01215051 https://hal.inria.fr/hal-01215051/document https://hal.inria.fr/hal-01215051/file/dmAO0146.pdf |
id |
ftccsdartic:oai:HAL:hal-01215051v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01215051v1 2023-05-15T16:50:29+02:00 The Incidence Hopf Algebra of Graphs Humpert, Brandon Martin, Jeremy L. Department of Mathematics (University of Kansas) University of Kansas Lawrence (KU) Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://hal.inria.fr/hal-01215051 https://hal.inria.fr/hal-01215051/document https://hal.inria.fr/hal-01215051/file/dmAO0146.pdf en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS hal-01215051 https://hal.inria.fr/hal-01215051 https://hal.inria.fr/hal-01215051/document https://hal.inria.fr/hal-01215051/file/dmAO0146.pdf info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215051 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.517-526 combinatorial Hopf algebra graph chromatic polynomial Tutte polynomial acyclic orientation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftccsdartic 2020-12-25T18:15:03Z International audience The graph algebra is a commutative, cocommutative, graded, connected incidence Hopf algebra, whose basis elements correspond to finite simple graphs and whose Hopf product and coproduct admit simple combinatorial descriptions. We give a new formula for the antipode in the graph algebra in terms of acyclic orientations; our formula contains many fewer terms than Schmitt's more general formula for the antipode in an incidence Hopf algebra. Applications include several formulas (some old and some new) for evaluations of the Tutte polynomial. L'algèbre de graphes est une algèbre d'incidence de Hopf commutative, cocommutative, graduée, et connexe, dont les éléments de base correspondent à des graphes finis simples et dont le produit et coproduit de Hopf admettent une description combinatoire simple. Nous présentons une nouvelle formule de l'antipode dans l'algèbre de graphes utilisant les orientations acycliques; notre formule contient beaucoup moins de termes que la formule générale de Schmitt pour l'antipode dans une algèbre d'incidence de Hopf. Les applications incluent plusieurs formules (connues et inconnues) pour les évaluations du polynôme de Tutte. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
combinatorial Hopf algebra graph chromatic polynomial Tutte polynomial acyclic orientation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
spellingShingle |
combinatorial Hopf algebra graph chromatic polynomial Tutte polynomial acyclic orientation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Humpert, Brandon Martin, Jeremy L. The Incidence Hopf Algebra of Graphs |
topic_facet |
combinatorial Hopf algebra graph chromatic polynomial Tutte polynomial acyclic orientation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] |
description |
International audience The graph algebra is a commutative, cocommutative, graded, connected incidence Hopf algebra, whose basis elements correspond to finite simple graphs and whose Hopf product and coproduct admit simple combinatorial descriptions. We give a new formula for the antipode in the graph algebra in terms of acyclic orientations; our formula contains many fewer terms than Schmitt's more general formula for the antipode in an incidence Hopf algebra. Applications include several formulas (some old and some new) for evaluations of the Tutte polynomial. L'algèbre de graphes est une algèbre d'incidence de Hopf commutative, cocommutative, graduée, et connexe, dont les éléments de base correspondent à des graphes finis simples et dont le produit et coproduit de Hopf admettent une description combinatoire simple. Nous présentons une nouvelle formule de l'antipode dans l'algèbre de graphes utilisant les orientations acycliques; notre formule contient beaucoup moins de termes que la formule générale de Schmitt pour l'antipode dans une algèbre d'incidence de Hopf. Les applications incluent plusieurs formules (connues et inconnues) pour les évaluations du polynôme de Tutte. |
author2 |
Department of Mathematics (University of Kansas) University of Kansas Lawrence (KU) Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel |
format |
Conference Object |
author |
Humpert, Brandon Martin, Jeremy L. |
author_facet |
Humpert, Brandon Martin, Jeremy L. |
author_sort |
Humpert, Brandon |
title |
The Incidence Hopf Algebra of Graphs |
title_short |
The Incidence Hopf Algebra of Graphs |
title_full |
The Incidence Hopf Algebra of Graphs |
title_fullStr |
The Incidence Hopf Algebra of Graphs |
title_full_unstemmed |
The Incidence Hopf Algebra of Graphs |
title_sort |
incidence hopf algebra of graphs |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/hal-01215051 https://hal.inria.fr/hal-01215051/document https://hal.inria.fr/hal-01215051/file/dmAO0146.pdf |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215051 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.517-526 |
op_relation |
hal-01215051 https://hal.inria.fr/hal-01215051 https://hal.inria.fr/hal-01215051/document https://hal.inria.fr/hal-01215051/file/dmAO0146.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766040629279719424 |