Book Sections Year : 2024

On counting orientations for graph homomorphisms and for dually embedded graphs using the Tutte polynomial of matroid perspectives

Emeric Gioan

Abstract

The goal of this note is to highlight applications to graph orientations of some recent results in oriented matroid perspectives, by providing adapted settings and a detailed example. An (oriented) matroid perspective (or morphism, or strong map, or quotient) is an ordered pair of (oriented) matroids satisfying some structural relationship. In the case of graphs, two notable types of perspectives can be considered: graph homomorphisms, and dually embedded graphs on a surface. The Tutte polynomial of such a perspective is a classical polynomial (also called Las Vergnas polynomial in the case of dually embedded graphs), whose coefficients and (some) evaluations are known to count pairs of orientations of certain types. We show how coefficients and (other) evaluations of the polynomial also count pairs of orientations of certain types where some edge orientations are fixed, as well as some equivalence classes of pairs of orientations of certain types. These properties appear when the edge set is linearly ordered.
Fichier principal
Vignette du fichier
Matrix Annals - Emeric Gioan v08 revision.pdf (138.83 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-04801903 , version 1 (25-11-2024)

Identifiers

  • HAL Id : lirmm-04801903 , version 1

Cite

Emeric Gioan. On counting orientations for graph homomorphisms and for dually embedded graphs using the Tutte polynomial of matroid perspectives. 2023 MATRIX Annals, Matrix Book Series (6), In press, 978-3-031-76737-1. ⟨lirmm-04801903⟩
5 View
11 Download

Share

More