For a graph cellularly embedded in an orientable surface, the packaged surface Tutte polynomial of Moffatt and Thompson admits deletion–contraction relations for every edge type, a Universality Property, and, as consequences, the first recursive computation of the numbers of nowhere-identity local flows and local tensions taking values in any finite group. The extension of this whole framework to non-orientable surfaces was stated as open in that work. Thompson's 2024 PhD thesis subsequently resolved the polynomial-level part: an Euler-genus version of the packaged surface Tutte polynomial is defined for non-orientable packaged ribbon graphs and satisfies deletion–contraction relations, duality, and universality without orientability hypotheses. What remains open is the analytic core: the signed-genus grading of the Goodall–Litjens–Regts–Vena surface Tutte polynomial — the invariant that enumerates local flows and tensions on non-orientable surfaces — is incompatible with recursive relations, and no deletion–contraction recurrences for these counts are known at the level of the embedded graphs, nor for any non-abelian group (for abelian groups the counts depend only on the underlying signed graph, for which signed-graph-level recurrences already exist). The problem is to find recursive deletion–contraction-type relations, with initial conditions, that compute the numbers of nowhere-identity local flows and local tensions of graphs cellularly embedded in non-orientable surfaces, for every finite group.

Background

The Tutte polynomial of a graph can be defined recursively: for an edge ee that is neither a bridge nor a loop, T(G)=T(G∖e)+T(G/e)T(G)=T(G\setminus e)+T(G/e), with separate rules for bridges and loops and base values on edgeless graphs. It is universal for graph parameters satisfying such deletion–contraction relations, and two of its classical evaluations count nowhere-zero group flows and proper vertex colourings (tensions) — the property for which Tutte originally introduced it as the dichromate.

When a graph is cellularly embedded in a surface (each face homeomorphic to an open disc), the natural analogues of flows and colourings are local flows and local tensions. A convenient combinatorial encoding of a cellular embedding is a ribbon graph: a surface with boundary assembled from vertex discs and edge discs glued along arcs, orientable or non-orientable according to the underlying surface. Directing the edge-ends (half-edges), a local Γ\Gamma-flow, for a finite (possibly non-abelian) group Γ\Gamma, is an assignment of group elements to the directed half-edges — the two half-edges of an edge receiving mutually inverse values — such that the product around each vertex, taken in the cyclic order induced by the embedding, is the identity; a local Γ\Gamma-tension is the dual condition, with the product around each boundary component (face) equal to the identity. The cyclic order makes both notions well-defined even for non-abelian groups, and a flow or tension is nowhere-identity (also called nowhere-zero) when no edge receives the identity element.

Goodall, Krajewski, Regts and Vena constructed a surface Tutte polynomial for maps — graphs cellularly embedded in orientable surfaces — whose evaluations give, for every finite group Γ\Gamma, the number qΓ(G)q_\Gamma(G) of nowhere-identity local Γ\Gamma-flows and the number pΓ(G)p_\Gamma(G) of nowhere-identity local Γ\Gamma-tensions; Goodall, Litjens, Regts and Vena extended it to non-orientable surfaces. This polynomial is defined by a state sum in which each connected component of a spanning subgraph contributes a monomial graded by its genus; in the non-orientable version the grading is by signed genus, equal to +g+g on orientable components of genus gg and −g-g on non-orientable ones. Unlike the classical Tutte polynomial, the surface Tutte polynomial admits no deletion–contraction relations for all edge types, and hence no full recursive definition or universality property; Goodall et al. explicitly asked what form such a recurrence could take. For abelian groups Γ\Gamma these counts depend only on the underlying signed graph of the embedding — the graph with each edge marked twisted or untwisted — and deletion–contraction recurrences at the signed-graph level are known; for non-abelian groups, whose counts genuinely involve the cyclic order at vertices, the signed-graph framework does not apply.

Moffatt and Thompson resolved the orientable case by enlarging the domain. A packaged ribbon graph is a ribbon graph together with a partition of its vertex set and a partition of its set of boundary components, each block carrying a non-negative integer weight; these objects describe graphs embedded in pseudo-surfaces (surfaces with finitely many pinch points) with vertex and face weights, building on the pseudo-surface and coloured-ribbon-graph theory of Huggett and Moffatt. For orientable packaged ribbon graphs they defined the packaged surface Tutte polynomial and proved: deletion–contraction relations valid for every edge type; a Universality Property, meaning every invariant of packaged ribbon graphs satisfying the deletion–contraction relations and the edgeless initial conditions is a specialization of it; specialization identities recovering the surface Tutte polynomial and the canonical Tutte polynomials of graphs in pseudo-surfaces (hence the Las Vergnas, Bollobás–Riordan and Krushkal polynomials); and, as consequences, the first deletion–contraction recurrences for qΓq_\Gamma and pΓp_\Gamma on orientable surfaces. Their development carries the standing convention that every ribbon graph is orientable, and they record that the extension of the polynomial, its deletion–contraction relations, universality, and the resulting recurrences for local flows and tensions to non-orientable surfaces is left open, with the non-orientable analysis to appear in the second author's PhD thesis.

That thesis (Thompson, Royal Holloway, 2024) settled the polynomial-level part: regrading the packaged surface Tutte polynomial by Euler genus γ=2k−v+e−b\gamma=2k-v+e-b (which, unlike orientable genus, is defined for non-orientable ribbon graphs) produces a polynomial of arbitrary, possibly non-orientable, packaged ribbon graphs that satisfies deletion–contraction relations for all edge types, duality, and a Universality Property — results on which Thompson's later published quasi-tree expansion relies. The specialization back to the surface Tutte polynomial is proved only for orientable ribbon graphs, however, and the flow-and-tension section of the thesis explicitly assumes orientability, with the remark that although flows and tensions in non-orientable ribbon graphs are understood in the literature, it is non-trivial to obtain recursive relations for them, so the non-orientable case is excluded entirely. The recorded obstruction is that the signed-genus grading that carries the non-orientable flow and tension counts is not compatible with recursive relations. What survives is precisely the non-orientable recurrence problem for the counts themselves, for every finite group; the abelian case admits recurrences through the signed-graph quotient, but these neither extend to non-abelian groups nor operate on the embedded graphs with their genus grading.

Problem Statement

Find recursive relations of deletion–contraction type, valid for every edge type of a graph cellularly embedded in a non-orientable surface (including non-orientable, i.e. twisted, loops) and with explicit initial conditions on edgeless graphs, that compute the number qΓ(G)q_\Gamma(G) of nowhere-identity local Γ\Gamma-flows and the number pΓ(G)p_\Gamma(G) of nowhere-identity local Γ\Gamma-tensions, for every finite group Γ\Gamma — the non-orientable counterpart of the recurrences Moffatt and Thompson established for orientable surfaces. The quantities computed must agree with the existing enumerations of Goodall–Litjens–Regts–Vena. This is the surviving component of the open problem stated in that source work — extending the packaged surface Tutte polynomial, its deletion–contraction relations, universality, and the resulting recurrences for local flows and tensions to non-orientable surfaces — the first three components having since been resolved in Thompson's thesis in Euler-genus form. The scope is every finite group, non-abelian groups included: for abelian groups the counts factor through the underlying signed graph of the embedding, for which deletion–contraction recurrences are already known, so an answer restricted to abelian groups, or operating only on the signed-graph quotient rather than on embedded graphs, does not meet the target. A natural route, not the only admissible one, is to construct a packaging-type extension of the surface Tutte polynomial that retains the orientability information carried by the signed genus while admitting deletion–contraction relations for all edge types, together with the specialization identities recovering the local flow and tension counts; an answer that instead proves the signed-genus polynomial itself admits no full recurrence does not thereby complete the task, whose goal remains recursive deletion–contraction-type relations computing qΓq_\Gamma and pΓp_\Gamma on non-orientable surfaces.

References

  1. Iain Moffatt and Maya Thompson, “Deletion–contraction and the surface Tutte polynomial”, European Journal of Combinatorics 118 (2024), article 103933. DOI: 10.1016/j.ejc.2024.103933; arXiv:2212.12371, https://arxiv.org/abs/2212.12371
  2. Maya Thompson, “Topological Analogues of the Tutte polynomial and their Decompositions”, PhD thesis, Royal Holloway, University of London, awarded March 2024. https://pure.royalholloway.ac.uk/en/publications/topological-analogues-of-the-tutte-polynomial-and-their-decomposi ; full text: https://pure.royalholloway.ac.uk/ws/files/59149237/2024thompsonmphd.pdf
  3. Andrew Goodall, Bart Litjens, Guus Regts and Lluís Vena, “A Tutte polynomial for maps II: The non-orientable case”, European Journal of Combinatorics 86 (2020), article 103095. DOI: 10.1016/j.ejc.2020.103095; arXiv:1804.01496, https://arxiv.org/abs/1804.01496
  4. Andrew Goodall, Thomas Krajewski, Guus Regts and Lluís Vena, “A Tutte polynomial for maps”, Combinatorics, Probability and Computing 27 (2018), 913–945. DOI: 10.1017/S0963548318000081; arXiv:1610.04486, https://arxiv.org/abs/1610.04486
  5. Maya Thompson, “A quasi-tree expansion for the surface Tutte polynomial”, Advances in Applied Mathematics 175 (2026), article 103045. DOI: 10.1016/j.aam.2026.103045; arXiv:2506.13748, https://arxiv.org/abs/2506.13748
  6. Stephen Huggett and Iain Moffatt, “Types of embedded graphs and their Tutte polynomials”, Mathematical Proceedings of the Cambridge Philosophical Society 169 (2020), 255–297. DOI: 10.1017/S0305004119000161
  7. Andrew Goodall, Bart Litjens, Guus Regts and Lluís Vena, “Tutte's dichromate for signed graphs”, Discrete Applied Mathematics 289 (2021), 153–184. DOI: 10.1016/j.dam.2020.09.021; arXiv:1903.07548, https://arxiv.org/abs/1903.07548
  8. Matt DeVos, Edita Rollová and Robert Šámal, “A Note on Counting Flows in Signed Graphs”, The Electronic Journal of Combinatorics 26(2) (2019), article P2.38. DOI: 10.37236/7958, https://doi.org/10.37236/7958