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. The Incidence Hopf A ...
Conference paper

The Incidence Hopf Algebra of Graphs

Brandon Humpert (1), Jeremy L. Martin ORCID (1)
(1) Department of Mathematics
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2010
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Proceedings
DOI
10.46298/dmtcs.2930
License
https://about.hal.science/hal-authorisation-v1
Indicators
775
Views
795
Downloads

The Incidence Hopf Algebra of Graphs

Brandon Humpert (1), Jeremy L. Martin ORCID (1)
(1) Department of Mathematics
Abstract
English
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.
French
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.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • combinatorial Hopf algebra
  • graph
  • chromatic polynomial
  • Tutte polynomial
  • acyclic orientation
Cited by

Source: OpenCitations

  • A Hopf algebra of subword complexes

    Advances in Mathematics

    Authors : Nantel Bergeron ORCID, Cesar Ceballos ORCID

    Journal reference : Volume 305, 2016, pp. 1163-1201

    DOI : 10.1016/j.aim.2016.10.007

  • Hopf algebras and topological recursion

    arXiv (Cornell University)

    Authors : João N Esteves

    Journal reference : Volume 48, 2015, pp. 445205

    DOI : 10.1088/1751-8113/48/44/445205

  • Increasing Trees and the Degree-Chromatic Polynomial

    Kazakh mathematical journal.

    Authors : Medet Jumadildayev

    Journal reference : Volume 25, 2025, pp. 57-66

    DOI : 10.70474/ev8j4t48

  • Antipodes and involutions

    arXiv (Cornell University)

    Authors : Carolina Benedetti, Bruce E. Sagan ORCID

    Journal reference : Volume 148, 2017, pp. 275-315

    DOI : 10.1016/j.jcta.2016.12.005

  • On the cancellation-free antipode formula for the Malvenuto–Reutenauer Hopf Algebra

    European Journal of Combinatorics

    Authors : Yu Houyi, Da Xu

    Journal reference : Volume 113, 2023, pp. 103745

    DOI : 10.1016/j.ejc.2023.103745

  • Combinatorial Hopf Algebras of Simplicial Complexes

    arXiv (Cornell University)

    Authors : Carolina Benedetti, Joshua Hallam, John Machacek

    Journal reference : Volume 30, 2016, pp. 1737-1757

    DOI : 10.1137/15m1038281

  • Hopf Monoids and Generalized Permutahedra

    Memoirs of the American Mathematical Society

    Authors : Marcelo Aguiar ORCID, Federico Ardila

    Journal reference : Volume 289, 2023, pp.

    DOI : 10.1090/memo/1437

  • Valuations and the Hopf Monoid of Generalized Permutahedra

    International Mathematics Research Notices

    Authors : Federico Ardila, Mario Sanchez ORCID

    Journal reference : Volume 2023, 2022, pp. 4149-4224

    DOI : 10.1093/imrn/rnab355

  • Decomposition Spaces and Restriction Species

    arXiv (Cornell University)

    Authors : Imma Gálvez-Carrillo ORCID, Joachim Kock ORCID, Andrew Tonks ORCID

    Journal reference : Volume 2020, 2018, pp. 7558-7616

    DOI : 10.1093/imrn/rny089

  • New invariants for permutations, orders and graphs

    arXiv (Cornell University)

    Authors : Jean-Christophe Aval, Nantel Bergeron ORCID, John Machacek

    Journal reference : Volume 121, 2020, pp. 102080

    DOI : 10.1016/j.aam.2020.102080

  • The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes

    arXiv (Cornell University)

    Authors : Raul Penaguiao ORCID

    Journal reference : Volume 175, 2020, pp. 105258

    DOI : 10.1016/j.jcta.2020.105258

  • A Hopf algebra on subgraphs of a graph

    Journal of Algebra and Its Applications

    Authors : Xiaomeng Wang ORCID, Shou-Jun Xu ORCID, Xing Gao ORCID

    Journal reference : Volume 19, 2019, pp. 2050164

    DOI : 10.1142/s0219498820501649

  • The antipode of linearized Hopf monoids

    Algebraic Combinatorics

    Authors : Carolina Benedetti, Nantel Bergeron ORCID

    Journal reference : Volume 2, 2019, pp. 903-935

    DOI : 10.5802/alco.53

  • CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS

    International Electronic Journal of Algebra

    Authors : Loic FOISSY ORCID

    Journal reference : Volume 30, 2021, pp. 116-167

    DOI : 10.24330/ieja.969651

  • Weighted quasisymmetric enumerator for generalized permutohedra

    Journal of Algebraic Combinatorics

    Authors : Vladimir Grujić ORCID, Marko Pešović ORCID, Tanja Stojadinović ORCID

    Journal reference : Volume 51, 2019, pp. 247-272

    DOI : 10.1007/s10801-019-00874-x

  • On the Hopf algebra of multi-complexes

    Journal of Algebraic Combinatorics

    Authors : Miodrag Iovanov, Jaiung Jun ORCID

    Journal reference : Volume 56, 2022, pp. 425-451

    DOI : 10.1007/s10801-022-01117-2
Preview
Loading PDF preview...