Polynomial invariants of cyclically ordered graphs
Paul Bratch, M. N. Ellingham, Joanna A. Ellis-Monaghan, Iain Moffatt, Wout Moltmaker · 2025
Read Polynomial invariants of cyclically ordered graphs by Paul Bratch, M. N. Ellingham, Joanna A. Ellis-Monaghan, Iain Moffatt, Wout Moltmaker (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13302.txt.
Introduction
Paul Bratch and 4 co-authors build a formal theory of cyclically ordered graphs, objects that sit between plain graphs and graphs drawn on surfaces. In such a graph, the edges at each vertex carry a cyclic order. The objects appear in topological graph theory, knot theory, and mathematical biology.
The authors set out several ways to present these graphs and show how each view helps build invariants, meaning numbers or polynomials that do not change under allowed moves. They adapt the matching, transition, and Yamada polynomials to this setting. The result gives workers in several fields a shared language and a tested set of tools.
Catalog record
| CREATOR | Paul Bratch, M. N. Ellingham, Joanna A. Ellis-Monaghan, Iain Moffatt, Wout Moltmaker |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13302
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Polynomial invariants of cyclically ordered graphs Paul Bratch, M. N. Ellingham, Joanna A. Ellis-Monaghan, Iain Moffatt, Wout Moltmaker Abstract . Cyclically ordered graphs, or cogs , sit between abstract graphs and cellularly embedded graphs. They arise naturally in topological graph theory, knot theory, and mathematical biology. We develop a formal theory of cogs and establish a number of invariants of cogs. In particular we detail several ways to present cogs and detail how these descriptions can be used to construct cog invariants by adapting the matching, transition and Yamada polynomials. 2020 Mathematics Subject Classification 05C10, 05C31 1. Introduction We develop the theory of cyclically ordered graphs, or cogs . Cogs arise in several distinct areas of mathematics including topological graph theory, knot theory, and mathematical biology. In this paper we consolidate the various approaches to cogs and present a common theory for them. We then define and analyse a range of polynomial-valued cog invariants that will serve as tools for further understanding the properties of cogs. A cog is an abstract graph with an undirected cyclic order at each vertex. Cogs sit between abstract graphs and graphs cellularly embedded in surfaces, where the latter can be described by graphs with not only (directed) cyclic orders at the vertices but also signs on the edges (see Subsection 2.1 for details). For example, while there is exactly one abstract graph with two edges and one vertex (up to graph isomorphism), and six cellular embeddings of this graph (up to equivalence), there are exactly two cogs derived from this graph (up to cog isomorphism, defined later). Our interest in cogs stems in part from topological graph theory and Chmutov’s partial duals [ 14 ] . It is a classical result that two embedded graphs are geometric duals (also known as Euler–Poincaré duals or surface duals) if and only if their medial graphs are equal as embedded graphs. If instead we ask when two embedded graphs are partial duals then this is characterised by their embedded medial graphs having isomorphic cogs (see [ 19 ] for details). Cogs also appear in the context of rigid vertex graphs in knot theory and in DNA applications, for example in [ 10 , 11 , 30 ] . Given the success of graph polynomials as tools for understanding graphs and cellularly embedded graphs, it is natural to seek polynomials that serve analogously for cogs. There are already many polynomials encoding information about abstract graphs, and also quite a few for graphs embedded in surfaces. However, we know of no prior polynomial that captures the intermediate structure, between abstract and embedded graphs, recorded by cogs. We begin filling this gap. The observation that cogs interpolate between abstract graphs and cellularly embedded graphs motivates our strategy for constructing polynomial invariants of cogs. We look either for ways to add structure to known abstract graph invariants so that they record information about the cog, or for ways to remove structure from known topological graph invariants so that they become cog invariants. Here we illustrate our strategies by constructing cog invariants arising from three very different invariants: the matching polynomial in Section 3 , the transition polynomial in Section 4 , and the Yamada polynomial in Section 5 . Each section demonstrates a different general approach to constructing cog invariants. We conclude with a discussion of some further directions of study in Section 6 . 2. Background In this section we review some common concepts from topological graph theory, give a formal definition of cogs, and contrast and compare cogs and cellularly embedded graphs. We conclude by defining graph-encoded cogs, or gecs, which give a description of cogs analogous to Lin’s description of embedded graphs as graph-encoded maps, or gems [ 31 ] . The different descriptions of cogs provide us with different approaches to constructing cog invariants in the subsequent sections. The key topological graph theoretic equivalences we review in this section may be summarised as follows. • Embedded graphs \leftrightarrow signed rotation systems up to vertex flips \leftrightarrow ribbon graphs. • Oriented embedded graphs \leftrightarrow rotation systems. • Orientable embedded graphs \leftrightarrow rotation systems up to component reversal. We show the following are equivalent. • Cogs. • Rotation systems up to vertex reversals. • Signed rotation systems up to vertex flips and arbitrarily changing edge signatures. • Ribbon graphs or embedded graphs up to taking partial Petrie duals. • Graph encoded cogs (gecs). We allow graphs to have multiple edges and loops, and think of each edge as consisting of two half-edges. Therefore, our formal definition of a graph G has a set of vertices V(G) , a set of half-edges that are paired into edges, with edge set E(G) , and an incidence function that maps each half-edge to a vertex. An isomorphism between graphs has a bijection between the vertex sets and a bijection between the sets of half-edges that preserve pairing into edges and incidence. We consider graphs up to isomorphism. In certain derived structures (gecs, generalised gecs, pointed-gecs and medial graphs) we also allow graphs to have free loops . A free loop is an edge that is not incident to any vertex. Free loops are often drawn as circles. Each free loop is considered to be a cycle of length 0 , and counts as a component of G . We write k(G) for the number of components of a graph G . We let G\mathbin{\backslash}e denote the graph obtained by deleting the edge e , and G/e denote the graph obtained by contracting the edge e . For a vertex v we let G\mathbin{\backslash}v denote the result of deleting v from G , that is removing v along with all its incident edges. For a set of edges A we write G\mathbin{\backslash}A , respectively G/A , for the result of deleting, respectively contracting, all of the edges in A . Similarly we write G\mathbin{\backslash}U for the result of deleting all the vertices in a set U of vertices. Finally, we let G\mathbin{\dagger}e denote the graph resulting from extracting an edge e=(u,v) from G , which is defined to be the graph G\mathbin{\backslash}\{u,v\} , where possibly u=v . Note that if e and f have no end points in common, then (G\mathbin{\dagger}e)\mathbin{\dagger}f=(G\mathbin{\dagger}f)\mathbin{\dagger}e=G\mathbin{\backslash}U , where U is the set of the endvertices of e and f . However, if e and f share any endvertices, then neither (G\mathbin{\dagger}e)\mathbin{\dagger}f nor (G\mathbin{\dagger}f)\mathbin{\dagger}e is defined. Surfaces in this paper are compact but not necessarily connected 2 -manifolds. If a surface can be given a globally consistent “clockwise” direction, it is orientable , and the surface together with the clockwise direction is an oriented surface . Otherwise the surface is nonorientable . Every connected orientable surface corresponds to two oriented surfaces, since there are two choices of clockwise direction. We assume that the reader is familiar with embeddings of graphs in surfaces and their various descriptions, and give only brief reminders of the constructions that are necessary here. All embeddings in this paper are cellular , with every face homeomorphic to an open disc, unless otherwise indicated. We consider embeddings up homeomorphisms of the surface that induce graph isomorphisms. When considering oriented embeddings , in oriented surfaces, the homeomorphisms