-
Polynomial invariants of cyclically ordered graphs
Authors:
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 adap…
▽ More
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.
△ Less
Submitted 17 November, 2025;
originally announced November 2025.
-
Tensor product formulas for the Bollobás-Riordan and Krushkal polynomials
Authors:
Iain Moffatt,
Maya Thompson
Abstract:
Brylawski's tensor product formula expresses the Tutte polynomial of the tensor product of two graphs in terms of Tutte polynomials arising from the tensor factors. Analogous tensor product formulas are known for the ribbon graph polynomial and transition polynomials of graphs embedded in surfaces, as well as for the Bollobás-Riordan polynomial in some special cases. We define the tensor product o…
▽ More
Brylawski's tensor product formula expresses the Tutte polynomial of the tensor product of two graphs in terms of Tutte polynomials arising from the tensor factors. Analogous tensor product formulas are known for the ribbon graph polynomial and transition polynomials of graphs embedded in surfaces, as well as for the Bollobás-Riordan polynomial in some special cases. We define the tensor product of graphs embedded in pseudo-surfaces and use this to generalize and unify all of the above results, providing Brylawski-style formulas for both the Bollobás-Riordan and Krushkal polynomials.
△ Less
Submitted 28 May, 2025;
originally announced May 2025.
-
Constructing a Tutte polynomial for graphs embedded in surfaces
Authors:
Iain Moffatt
Abstract:
There are several different extensions of the Tutte polynomial to graphs embedded in surfaces. To help frame the different options, here we consider the problem of extending the Tutte polynomial to cellularly embedded graphs starting from first principles. We offer three different routes to defining such a polynomial and show that they all lead to the same polynomial. This resulting polynomial is…
▽ More
There are several different extensions of the Tutte polynomial to graphs embedded in surfaces. To help frame the different options, here we consider the problem of extending the Tutte polynomial to cellularly embedded graphs starting from first principles. We offer three different routes to defining such a polynomial and show that they all lead to the same polynomial. This resulting polynomial is known in the literature under a few different names including the ribbon graph polynomial, and 2-variable Bollobas-Riordan polynomial.
Our overall aim here is to use this discussion as a mechanism for providing a gentle introduction to the topic of Tutte polynomials for graphs embedded in surfaces.
△ Less
Submitted 21 February, 2025;
originally announced February 2025.
-
An activities expansion of the transition polynomial of a multimatroid
Authors:
Criel Merino,
Iain Moffatt,
Steven Noble
Abstract:
The weighted transition polynomial of a multimatroid is a generalization of the Tutte polynomial. By defining the activity of a skew class with respect to a basis in a multimatroid, we obtain an activities expansion for the weighted transition polynomial. We also decompose the set of all transversals of a multimatroid as a union of subsets of transversals. Each term in the decomposition has the st…
▽ More
The weighted transition polynomial of a multimatroid is a generalization of the Tutte polynomial. By defining the activity of a skew class with respect to a basis in a multimatroid, we obtain an activities expansion for the weighted transition polynomial. We also decompose the set of all transversals of a multimatroid as a union of subsets of transversals. Each term in the decomposition has the structure of a boolean lattice, and each transversal belongs to a number of terms depending only on the sizes of some of its skew classes. Further expressions for the transition polynomial of a multimatroid are obtained via an equivalence relation on its bases and by extending Kochol's theory of compatible sets.
We apply our multimatroid results to obtain a result of Morse about the transition polynomial of a delta-matroid and get a partition of the boolean lattice of subsets of elements of a delta-matroid determined by the feasible sets. Finally, we describe how multimatroids arise from graphs embedded in surfaces and apply our results to obtain an activities expansion for the topological transition polynomial. Our work extends results for the Tutte polynomial of a matroid.
△ Less
Submitted 21 February, 2025; v1 submitted 9 August, 2024;
originally announced August 2024.
-
A coarse Tutte polynomial for hypermaps
Authors:
Joanna A. Ellis-Monaghan,
Iain Moffatt,
Steven Noble
Abstract:
We give an analogue of the Tutte polynomial for hypermaps. This polynomial can be defined as either a sum over subhypermaps, or recursively through deletion-contraction reductions where the terminal forms consist of isolated vertices. Our Tutte polynomial extends the classical Tutte polynomial of a graph as well as the Tutte polynomial of an embedded graph (i.e., the ribbon graph polynomial), and…
▽ More
We give an analogue of the Tutte polynomial for hypermaps. This polynomial can be defined as either a sum over subhypermaps, or recursively through deletion-contraction reductions where the terminal forms consist of isolated vertices. Our Tutte polynomial extends the classical Tutte polynomial of a graph as well as the Tutte polynomial of an embedded graph (i.e., the ribbon graph polynomial), and it is a specialization of the transition polynomial via a medial map transformation. We give hypermap duality and partial duality identities for our polynomial, as well as some evaluations, and examine relations between our polynomial and other hypermap polynomials.
△ Less
Submitted 9 August, 2024; v1 submitted 29 March, 2024;
originally announced April 2024.
-
Tensor products of multimatroids and a Brylawski-type formula for the transition polynomial
Authors:
Iain Moffatt,
Steven Noble,
Maya Thompson
Abstract:
Brylawski's tensor product formula expresses the Tutte polynomial of the tensor product of two graphs or matroids in terms of Tutte polynomials arising from the tensor factors. Analogous tensor product formulas are known for the Bollobas-Riordan and transition polynomials of graphs embedded in surfaces. We show that these formulas are instances of a more general result for multimatroids by giving…
▽ More
Brylawski's tensor product formula expresses the Tutte polynomial of the tensor product of two graphs or matroids in terms of Tutte polynomials arising from the tensor factors. Analogous tensor product formulas are known for the Bollobas-Riordan and transition polynomials of graphs embedded in surfaces. We show that these formulas are instances of a more general result for multimatroids by giving a tensor product formula for the multimatroid transition polynomial and showing that Brylawski's formula and its topological analogues arise from it. Along the way we provide formulas for the transition polynomial of the two-sum and star product of multimatroids.
△ Less
Submitted 7 August, 2026; v1 submitted 1 September, 2023;
originally announced September 2023.
-
The critical group of a combinatorial map
Authors:
Criel Merino,
Iain Moffatt,
Steven Noble
Abstract:
Motivated by the appearance of embeddings in the theory of chip firing and the critical group of a graph, we introduce a version of the critical group (or sandpile group) for combinatorial maps, that is, for graphs embedded in orientable surfaces. We provide several definitions of our critical group, by approaching it through analogues of the cycle-cocycle matrix, the Laplacian matrix, and as the…
▽ More
Motivated by the appearance of embeddings in the theory of chip firing and the critical group of a graph, we introduce a version of the critical group (or sandpile group) for combinatorial maps, that is, for graphs embedded in orientable surfaces. We provide several definitions of our critical group, by approaching it through analogues of the cycle-cocycle matrix, the Laplacian matrix, and as the group of critical states of a chip firing game (or sandpile model) on the edges of a map.
Our group can be regarded as a perturbation of the classical critical group of its underlying graph by topological information, and it agrees with the classical critical group in the plane case. Its cardinality is equal to the number of spanning quasi-trees in a connected map, just as the cardinality of the classical critical group is equal to the number of spanning trees of a connected graph.
Our approach exploits the properties of principally unimodular matrices and the methods of delta-matroid theory.
△ Less
Submitted 18 March, 2025; v1 submitted 25 August, 2023;
originally announced August 2023.
-
Types of embedded graphs and their Tutte polynomials
Authors:
Stephen Huggett,
Iain Moffatt
Abstract:
We take an elementary and systematic approach to the problem of extending the Tutte polynomial to the setting of embedded graphs. Four notions of embedded graphs arise naturally when considering deletion and contraction operations on graphs on surfaces. We give a description of each class in terms of coloured ribbon graphs. We then identify a universal deletion-contraction invariant (i.e., a `Tutt…
▽ More
We take an elementary and systematic approach to the problem of extending the Tutte polynomial to the setting of embedded graphs. Four notions of embedded graphs arise naturally when considering deletion and contraction operations on graphs on surfaces. We give a description of each class in terms of coloured ribbon graphs. We then identify a universal deletion-contraction invariant (i.e., a `Tutte polynomial') for each class. We relate these to graph polynomials in the literature, including the Bollobás--Riordan, Krushkal, and Las Vergnas polynomials, and give state-sum formulations, duality relations, deleton-contraction relations, and quasi-tree expansions for each of them.
△ Less
Submitted 29 December, 2022;
originally announced December 2022.
-
Deletion-Contraction and the Surface Tutte Polynomial
Authors:
Iain Moffatt,
Maya Thompson
Abstract:
In this paper we unify two families of topological Tutte polynomials. The first family is that coming from the surface Tutte polynomial, a polynomial that arises in the theory of local flows and tensions. The second family arises from the canonical Tutte polynomials of Hopf algebras. Each family includes the Las Vergnas, Bollobás-Riordan, and Krushkal polynomials. As a consequence we determine a d…
▽ More
In this paper we unify two families of topological Tutte polynomials. The first family is that coming from the surface Tutte polynomial, a polynomial that arises in the theory of local flows and tensions. The second family arises from the canonical Tutte polynomials of Hopf algebras. Each family includes the Las Vergnas, Bollobás-Riordan, and Krushkal polynomials. As a consequence we determine a deletion-contraction definition of the surface Tutte polynomial and recursion relations for the number of local flows and tensions in an embedded graph.
△ Less
Submitted 25 January, 2024; v1 submitted 23 December, 2022;
originally announced December 2022.
-
Irreducibility of the Tutte polynomial of an embedded graph
Authors:
Joanna A. Ellis-Monaghan,
Andrew J. Goodall,
Iain Moffatt,
Steven Noble,
Lluís Vena
Abstract:
We prove that the ribbon graph polynomial of a graph embedded in an orientable surface is irreducible if and only if the embedded graph is neither the disjoint union nor the join of embedded graphs. This result is analogous to the fact that the Tutte polynomial of a graph is irreducible if and only if the graph is connected and non-separable.
We prove that the ribbon graph polynomial of a graph embedded in an orientable surface is irreducible if and only if the embedded graph is neither the disjoint union nor the join of embedded graphs. This result is analogous to the fact that the Tutte polynomial of a graph is irreducible if and only if the graph is connected and non-separable.
△ Less
Submitted 21 December, 2022;
originally announced December 2022.
-
A 2-isomorphism theorem for delta-matroids
Authors:
Iain Moffatt,
Jaeseong Oh
Abstract:
Whitney's 2-Isomorphism Theorem characterises when two graphs have isomorphic cycle matroids. We present an analogue of this theorem for graphs embedded in surfaces by characterising when two graphs in surface have isomorphic delta-matroids.
Whitney's 2-Isomorphism Theorem characterises when two graphs have isomorphic cycle matroids. We present an analogue of this theorem for graphs embedded in surfaces by characterising when two graphs in surface have isomorphic delta-matroids.
△ Less
Submitted 9 October, 2019;
originally announced October 2019.
-
Edge colourings and topological graph polynomials
Authors:
Joanna A. Ellis-Monaghan,
Louis H. Kauffman,
Iain Moffatt
Abstract:
A k-valuation is a special type of edge k-colouring of a medial graph. Various graph polynomials, such as the Tutte, Penrose, Bollobás-Riordan, and transition polynomials, admit combinatorial interpretations and evaluations as weighted counts of k-valuations. In this paper, we consider a multivariate generating function of k-valuations. We show that this is a polynomial in k and hence defines a gr…
▽ More
A k-valuation is a special type of edge k-colouring of a medial graph. Various graph polynomials, such as the Tutte, Penrose, Bollobás-Riordan, and transition polynomials, admit combinatorial interpretations and evaluations as weighted counts of k-valuations. In this paper, we consider a multivariate generating function of k-valuations. We show that this is a polynomial in k and hence defines a graph polynomial. We then show that the resulting polynomial has several desirable properties, including a recursive deletion-contraction-type definition, and specialises to the graph polynomials mentioned above. It also offers an alternative extension of the Penrose polynomial from plane graphs to graphs in other surfaces.
△ Less
Submitted 19 July, 2018;
originally announced July 2018.
-
The structure of delta-matroids with width one twists
Authors:
Carolyn Chun,
Rhiannon Hall,
Criel Merino,
Iain Moffatt,
Steven Noble
Abstract:
The width of a delta-matroid is the difference in size between a maximal and minimal feasible set. We give a Rough Structure Theorem for delta-matroids that admit a twist of width one. We apply this theorem to give an excluded minor characterisation of delta-matroids that admit a twist of width at most one.
The width of a delta-matroid is the difference in size between a maximal and minimal feasible set. We give a Rough Structure Theorem for delta-matroids that admit a twist of width one. We apply this theorem to give an excluded minor characterisation of delta-matroids that admit a twist of width at most one.
△ Less
Submitted 25 May, 2017;
originally announced May 2017.
-
Non-peripheral ideal decompositions of alternating knots
Authors:
Stavros Garoufalidis,
Iain Moffatt,
Dylan P. Thurston
Abstract:
An ideal triangulation $\mathcal{T}$ of a hyperbolic 3-manifold $M$ with one cusp is non-peripheral if no edge of $\mathcal{T}$ is homotopic to a curve in the boundary torus of $M$. For such a triangulation, the gluing and completeness equations can be solved to recover the hyperbolic structure of $M$. A planar projection of a knot gives four ideal cell decompositions of its complement (minus 2 ba…
▽ More
An ideal triangulation $\mathcal{T}$ of a hyperbolic 3-manifold $M$ with one cusp is non-peripheral if no edge of $\mathcal{T}$ is homotopic to a curve in the boundary torus of $M$. For such a triangulation, the gluing and completeness equations can be solved to recover the hyperbolic structure of $M$. A planar projection of a knot gives four ideal cell decompositions of its complement (minus 2 balls), two of which are ideal triangulations that use 4 (resp., 5) ideal tetrahedra per crossing. Our main result is that these ideal triangulations are non-peripheral for all planar, reduced, alternating projections of hyperbolic knots. Our proof uses the small cancellation properties of the Dehn presentation of alternating knot groups, and an explicit solution to their word and conjugacy problems. In particular, we describe a planar complex that encodes all geodesic words that represent elements of the peripheral subgroup of an alternating knot group. This gives a polynomial time algorithm for checking if an element in an alternating knot group is peripheral. Our motivation for this work comes from the Volume Conjecture for knots.
△ Less
Submitted 31 October, 2016;
originally announced October 2016.
-
On the interplay between embedded graphs and delta-matroids
Authors:
Carolyn Chun,
Iain Moffatt,
Steven D. Noble,
Ralf Rueckriemen
Abstract:
The mutually enriching relationship between graphs and matroids has motivated discoveries in both fields. In this paper, we exploit the similar relationship between embedded graphs and delta-matroids. There are well-known connections between geometric duals of plane graphs and duals of matroids. We obtain analogous connections for various types of duality in the literature for graphs in surfaces o…
▽ More
The mutually enriching relationship between graphs and matroids has motivated discoveries in both fields. In this paper, we exploit the similar relationship between embedded graphs and delta-matroids. There are well-known connections between geometric duals of plane graphs and duals of matroids. We obtain analogous connections for various types of duality in the literature for graphs in surfaces of higher genus and delta-matroids. Using this interplay, we establish a rough structure theorem for delta-matroids that are twists of matroids, we translate Petrie duality on ribbon graphs to loop complementation on delta-matroids, and we prove that ribbon graph polynomials, such as the Penrose polynomial, the characteristic polynomial, and the transition polynomial, are in fact delta-matroidal. We also express the Penrose polynomial as a sum of characteristic polynomials.
△ Less
Submitted 1 March, 2019; v1 submitted 3 February, 2016;
originally announced February 2016.
-
Handle slides for delta-matroids
Authors:
Iain Moffatt,
Eunice Mphako-Banda
Abstract:
A classic exercise in the topology of surfaces is to show that, using handle slides, every disc-band surface, or 1-vertex ribbon graph, can be put in a canonical form consisting of the connected sum of orientable loops, and either non-orientable loops or pairs of interlaced orientable loops. Motivated by the principle that ribbon graph theory informs delta-matroid theory, we find the delta-matroid…
▽ More
A classic exercise in the topology of surfaces is to show that, using handle slides, every disc-band surface, or 1-vertex ribbon graph, can be put in a canonical form consisting of the connected sum of orientable loops, and either non-orientable loops or pairs of interlaced orientable loops. Motivated by the principle that ribbon graph theory informs delta-matroid theory, we find the delta-matroid analogue of this surface classification. We show that, using a delta-matroid analogue of handle-slides, every binary delta-matroid in which the empty set is feasible can be written in a canonical form consisting of the direct sum of the delta-matroids of orientable loops, and either non-orientable loops or pairs of interlaced orientable loops. Our delta-matroid results are compatible with the surface results in the sense that they are their ribbon graphic delta-matroidal analogues.
△ Less
Submitted 1 May, 2017; v1 submitted 25 October, 2015;
originally announced October 2015.
-
Hopf algebras and Tutte polynomials
Authors:
Thomas Krajewski,
Iain Moffatt,
Adrian Tanasa
Abstract:
By considering Tutte polynomials of Hopf algebras, we show how a Tutte polynomial can be canonically associated with combinatorial objects that have some notions of deletion and contraction. We show that several graph polynomials from the literature arise from this framework. These polynomials include the classical Tutte polynomial of graphs and matroids, Las Vergnas' Tutte polynomial of the morph…
▽ More
By considering Tutte polynomials of Hopf algebras, we show how a Tutte polynomial can be canonically associated with combinatorial objects that have some notions of deletion and contraction. We show that several graph polynomials from the literature arise from this framework. These polynomials include the classical Tutte polynomial of graphs and matroids, Las Vergnas' Tutte polynomial of the morphism of matroids and his Tutte polynomial for embedded graphs, Bollobas and Riordan's ribbon graph polynomial, the Krushkal polynomial, and the Penrose polynomial.
We show that our Tutte polynomials of Hopf algebras share common properties with the classical Tutte polynomial, including deletion-contraction definitions, universality properties, convolution formulas, and duality relations. New results for graph polynomials from the literature are then obtained as examples of the general results.
Our results offer a framework for the study of the Tutte polynomial and its analogues in other settings, offering the means to determine the properties and connections between a wide class of polynomial invariants.
△ Less
Submitted 18 December, 2017; v1 submitted 4 August, 2015;
originally announced August 2015.
-
On the ribbon graphs of links in real projective space
Authors:
Iain Moffatt,
Johanna Strömberg
Abstract:
Every link diagram can be represented as a signed ribbon graph. However, different link diagrams can be represented by the same ribbon graphs. We determine how checkerboard colourable diagrams of links in real projective space, and virtual link diagrams, that are represented by the same ribbon graphs are related to each other. We also find moves that relate the diagrams of links in real projective…
▽ More
Every link diagram can be represented as a signed ribbon graph. However, different link diagrams can be represented by the same ribbon graphs. We determine how checkerboard colourable diagrams of links in real projective space, and virtual link diagrams, that are represented by the same ribbon graphs are related to each other. We also find moves that relate the diagrams of links in real projective space that give rise to (all-A) ribbon graphs with exactly one vertex.
△ Less
Submitted 6 February, 2015;
originally announced February 2015.
-
Ribbon graph minors and low-genus partial duals
Authors:
Iain Moffatt
Abstract:
We give an excluded minor characterisation of the class of ribbon graphs that admit partial duals of Euler genus at most one.
We give an excluded minor characterisation of the class of ribbon graphs that admit partial duals of Euler genus at most one.
△ Less
Submitted 1 February, 2015;
originally announced February 2015.
-
A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model
Authors:
Joanna A. Ellis-Monaghan,
Iain Moffatt
Abstract:
Here we observe that list coloring in graph theory coincides with the zero-temperature antiferromagnetic Potts model with an external field. We give a list coloring polynomial that equals the partition function in this case. This is analogous to the well-known connection between the chromatic polynomial and the zero-temperature, zero-field, antiferromagnetic Potts model. The subsequent cross ferti…
▽ More
Here we observe that list coloring in graph theory coincides with the zero-temperature antiferromagnetic Potts model with an external field. We give a list coloring polynomial that equals the partition function in this case. This is analogous to the well-known connection between the chromatic polynomial and the zero-temperature, zero-field, antiferromagnetic Potts model. The subsequent cross fertilization yields immediate results for the Potts model and suggests new research directions in list coloring.
△ Less
Submitted 1 August, 2014; v1 submitted 20 June, 2014;
originally announced June 2014.
-
Matroids, Delta-matroids and Embedded Graphs
Authors:
Carolyn Chun,
Iain Moffatt,
Steven D. Noble,
Ralf Rueckriemen
Abstract:
Matroid theory is often thought of as a generalization of graph theory. In this paper we propose an analogous correspondence between embedded graphs and delta-matroids. We show that delta-matroids arise as the natural extension of graphic matroids to the setting of embedded graphs. We show that various basic ribbon graph operations and concepts have delta-matroid analogues, and illustrate how the…
▽ More
Matroid theory is often thought of as a generalization of graph theory. In this paper we propose an analogous correspondence between embedded graphs and delta-matroids. We show that delta-matroids arise as the natural extension of graphic matroids to the setting of embedded graphs. We show that various basic ribbon graph operations and concepts have delta-matroid analogues, and illustrate how the connections between embedded graphs and delta-matroids can be exploited. Also, in direct analogy with the fact that The Tutte polynomial is matroidal, we show that several polynomials of embedded graphs from the literature, including the Las Vergnas, Bollabas-Riordan and Krushkal polynomials, are in fact delta-matroidal.
△ Less
Submitted 1 March, 2019; v1 submitted 4 March, 2014;
originally announced March 2014.
-
The Potts model and chromatic functions of graphs
Authors:
Martin Klazar,
Martin Loebl,
Iain Moffatt
Abstract:
The $U$-polynomial of Noble and Welsh is known to have intimate connections with the Potts model as well as with several important graph polynomials. For each graph $G$, $U(G)$ is equivalent to Stanley's symmetric bad colouring polynomial $XB(G)$. Moreover Sarmiento established the equivalence between $U$ and the polychromate of Brylawski. Loebl defined the $q$-dichromate $B_q(G,x,y)$ as a functio…
▽ More
The $U$-polynomial of Noble and Welsh is known to have intimate connections with the Potts model as well as with several important graph polynomials. For each graph $G$, $U(G)$ is equivalent to Stanley's symmetric bad colouring polynomial $XB(G)$. Moreover Sarmiento established the equivalence between $U$ and the polychromate of Brylawski. Loebl defined the $q$-dichromate $B_q(G,x,y)$ as a function of a graph $G$ and three independent variables $q,x,y$, proved that it is equal to the partition function of the Potts model with variable number of states and with a certain external field contribution, and conjectured that the $q$-dichromate is equivalent to the $U$-polynomial. He also proposed a stronger conjecture on integer partitions. The aim of this paper is two-fold. We present a construction disproving Loebl's integer partitions conjecture, and we introduce a new function $B_{r,q}(G;x,k)$ which is also equal to the partition function of the Potts model with variable number of states and with a (different) external field contribution, and we show that $B_{r,q}(G;x,k)$ is equivalent to the $U$-polynomial and to Stanley's symmetric bad colouring polynomial.
△ Less
Submitted 18 November, 2013;
originally announced November 2013.
-
The Las Vergnas Polynomial for embedded graphs
Authors:
Joanna A. Ellis-Monaghan,
Iain Moffatt
Abstract:
The Las Vergnas polynomial is an extension of the Tutte polynomial to cellularly embedded graphs. It was introduced by Michel Las Vergnas in 1978 as special case of his Tutte polynomial of a morphism of matroids. While the general Tutte polynomial of a morphism of matroids has a complete set of deletion-contraction relations, its specialisation to cellularly embedded graphs does not. Here we exten…
▽ More
The Las Vergnas polynomial is an extension of the Tutte polynomial to cellularly embedded graphs. It was introduced by Michel Las Vergnas in 1978 as special case of his Tutte polynomial of a morphism of matroids. While the general Tutte polynomial of a morphism of matroids has a complete set of deletion-contraction relations, its specialisation to cellularly embedded graphs does not. Here we extend the Las Vergnas polynomial to graphs in pseudo-surfaces. We show that in this setting we can define deletion and contraction for embedded graphs consistently with the deletion and contraction of the underlying matroid perspective, thus yielding a version of the Las Vergnas polynomial with complete recursive definition. This also enables us to obtain a deeper understanding of the relationships among the Las Vergnas polynomial, the Bollobas-Riordan polynomial, and the Krushkal polynomial. We also take this opportunity to extend some of Las Vergnas' results on Eulerian circuits from graphs in surfaces of low genus to surfaces of arbitrary genus.
△ Less
Submitted 13 November, 2014; v1 submitted 15 November, 2013;
originally announced November 2013.
-
Excluded minors and the ribbon graphs of knots
Authors:
Iain Moffatt
Abstract:
In this paper we consider minors of ribbon graphs (or, equivalently, cellularly embedded graphs). The theory of minors of ribbon graphs differs from that of graphs in that contracting loops is necessary and doing this can create additional vertices and components. Thus the ribbon graph minor relation is incompatible with the graph minor relation. We discuss excluded minor characterisations of mino…
▽ More
In this paper we consider minors of ribbon graphs (or, equivalently, cellularly embedded graphs). The theory of minors of ribbon graphs differs from that of graphs in that contracting loops is necessary and doing this can create additional vertices and components. Thus the ribbon graph minor relation is incompatible with the graph minor relation. We discuss excluded minor characterisations of minor closed families of ribbon graphs. Our main result is an excluded minor characterisation of the family of ribbon graphs that represent knot and link diagrams.
△ Less
Submitted 7 February, 2015; v1 submitted 9 November, 2013;
originally announced November 2013.
-
DNA origami and the complexity of Eulerian circuits with turning costs
Authors:
Joanna A. Ellis-Monaghan,
Andrew McDowell,
Iain Moffatt,
Greta Pangborn
Abstract:
Building a structure using self-assembly of DNA molecules by origami folding requires finding a route for the scaffolding strand through the desired structure. When the target structure is a 1-complex (or the geometric realization of a graph), an optimal route corresponds to an Eulerian circuit through the graph with minimum turning cost. By showing that it leads to a solution to the 3-SAT problem…
▽ More
Building a structure using self-assembly of DNA molecules by origami folding requires finding a route for the scaffolding strand through the desired structure. When the target structure is a 1-complex (or the geometric realization of a graph), an optimal route corresponds to an Eulerian circuit through the graph with minimum turning cost. By showing that it leads to a solution to the 3-SAT problem, we prove that the general problem of finding an optimal route for a scaffolding strand for such structures is NP-hard. We then show that the problem may readily be transformed into a Traveling Salesman Problem (TSP), so that machinery that has been developed for the TSP may be applied to find optimal routes for the scaffolding strand in a DNA origami self-assembly process. We give results for a few special cases, showing for example that the problem remains intractable for graphs with maximum degree 8, but is polynomial time for 4-regular plane graphs if the circuit is restricted to following faces. We conclude with some implications of these results for related problems, such as biomolecular computing and mill routing problems.
△ Less
Submitted 1 June, 2014; v1 submitted 18 September, 2013;
originally announced September 2013.
-
Separability and the genus of a partial dual
Authors:
Iain Moffatt
Abstract:
Partial duality generalizes the fundamental concept of the geometric dual of an embedded graph. A partial dual is obtained by forming the geometric dual with respect to only a subset of edges. While geometric duality preserves the genus of an embedded graph, partial duality does not. Here we are interested in the problem of determining which edge sets of an embedded graph give rise to a partial du…
▽ More
Partial duality generalizes the fundamental concept of the geometric dual of an embedded graph. A partial dual is obtained by forming the geometric dual with respect to only a subset of edges. While geometric duality preserves the genus of an embedded graph, partial duality does not. Here we are interested in the problem of determining which edge sets of an embedded graph give rise to a partial dual of a given genus. This problem turns out to be intimately connected to the separability of the embedded graph. We determine how separability is related to the genus of a partial dual. We use this to characterize partial duals of graphs embedded in the plane, and in the real projective plane, in terms of a particular type of separation of an embedded graph. These characterizations are then used to determine a local move relating all partially dual graphs in the plane and in the real projective plane.
△ Less
Submitted 8 September, 2012; v1 submitted 17 August, 2011;
originally announced August 2011.
-
Evaluations of topological Tutte polynomials
Authors:
Joanna A. Ellis-Monaghan,
Iain Moffatt
Abstract:
We find new properties of the topological transition polynomial of embedded graphs, $Q(G)$. We use these properties to explain the striking similarities between certain evaluations of Bollobás and Riordan's ribbon graph polynomial, $R(G)$, and the topological Penrose polynomial, $P(G)$. The general framework provided by $Q(G)$ also leads to several other combinatorial interpretations these polynom…
▽ More
We find new properties of the topological transition polynomial of embedded graphs, $Q(G)$. We use these properties to explain the striking similarities between certain evaluations of Bollobás and Riordan's ribbon graph polynomial, $R(G)$, and the topological Penrose polynomial, $P(G)$. The general framework provided by $Q(G)$ also leads to several other combinatorial interpretations these polynomials. In particular, we express $P(G)$, $R(G)$, and the Tutte polynomial, $T(G)$, as sums of chromatic polynomials of graphs derived from $G$; show that these polynomials count $k$-valuations of medial graphs; show that $R(G)$ counts edge 3-colourings; and reformulate the Four Colour Theorem in terms of $R(G)$. We conclude with a reduction formula for the transition polynomial of the tensor product of two embedded graphs, showing that it leads to additional relations among these polynomials and to further combinatorial interpretations of $P(G)$ and $R(G)$.
△ Less
Submitted 8 June, 2014; v1 submitted 16 August, 2011;
originally announced August 2011.
-
On the Potts model partition function in an external field
Authors:
Leslie M. McDonald,
Iain Moffatt
Abstract:
We study the partition function of Potts model in an external (magnetic) field, and its connections with the zero-field Potts model partition function. Using a deletion-contraction formulation for the partition function Z for this model, we show that it can be expanded in terms of the zero-field partition function. We also show that Z can be written as a sum over the spanning trees, and the spanni…
▽ More
We study the partition function of Potts model in an external (magnetic) field, and its connections with the zero-field Potts model partition function. Using a deletion-contraction formulation for the partition function Z for this model, we show that it can be expanded in terms of the zero-field partition function. We also show that Z can be written as a sum over the spanning trees, and the spanning forests, of a graph G. Our results extend to Z the well-known spanning tree expansion for the zero-field partition function that arises though its connections with the Tutte polynomial.
△ Less
Submitted 26 January, 2012; v1 submitted 12 July, 2011;
originally announced July 2011.
-
A Penrose polynomial for embedded graphs
Authors:
Joanna A. Ellis-Monaghan,
Iain Moffatt
Abstract:
We extend the Penrose polynomial, originally defined only for plane graphs, to graphs embedded in arbitrary surfaces. Considering this Penrose polynomial of embedded graphs leads to new identities and relations for the Penrose polynomial which can not be realized within the class of plane graphs. In particular, by exploiting connections with the transition polynomial and the ribbon group action, w…
▽ More
We extend the Penrose polynomial, originally defined only for plane graphs, to graphs embedded in arbitrary surfaces. Considering this Penrose polynomial of embedded graphs leads to new identities and relations for the Penrose polynomial which can not be realized within the class of plane graphs. In particular, by exploiting connections with the transition polynomial and the ribbon group action, we find a deletion-contraction-type relation for the Penrose polynomial. We relate the Penrose polynomial of an orientable checkerboard colourable graph to the circuit partition polynomial of its medial graph and use this to find new combinatorial interpretations of the Penrose polynomial. We also show that the Penrose polynomial of a plane graph G can be expressed as a sum of chromatic polynomials of twisted duals of G. This allows us to obtain a new reformulation of the Four Colour Theorem.
△ Less
Submitted 15 July, 2012; v1 submitted 26 June, 2011;
originally announced June 2011.
-
On the Seifert graphs of a link diagram and its parallels
Authors:
Stephen Huggett,
Iain Moffatt,
Natalia Virdee
Abstract:
Recently, Dasbach, Futer, Kalfagianni, Lin, and Stoltzfus extended the notion of a Tait graph by associating a set of ribbon graphs (or equivalently, embedded graphs) to a link diagram. Here we focus on Seifert graphs, which are the ribbon graphs of a knot or link diagram that arise from Seifert states. We provide a characterization of Seifert graphs in terms of Eulerian subgraphs. This characteri…
▽ More
Recently, Dasbach, Futer, Kalfagianni, Lin, and Stoltzfus extended the notion of a Tait graph by associating a set of ribbon graphs (or equivalently, embedded graphs) to a link diagram. Here we focus on Seifert graphs, which are the ribbon graphs of a knot or link diagram that arise from Seifert states. We provide a characterization of Seifert graphs in terms of Eulerian subgraphs. This characterization can be viewed as a refinement of the fact that Seifert graphs are bipartite. We go on to examine the family of ribbon graphs that arises by forming the parallels of a link diagram and determine how the genus of the ribbon graph of a $r$-fold parallel of a link diagram is related to that of the original link diagram.
△ Less
Submitted 21 June, 2011;
originally announced June 2011.
-
Bipartite partial duals and circuits in medial graphs
Authors:
Stephen Huggett,
Iain Moffatt
Abstract:
It is well known that a plane graph is Eulerian if and only if its geometric dual is bipartite. We extend this result to partial duals of plane graphs. We then characterize all bipartite partial duals of a plane graph in terms of oriented circuits in its medial graph.
It is well known that a plane graph is Eulerian if and only if its geometric dual is bipartite. We extend this result to partial duals of plane graphs. We then characterize all bipartite partial duals of a plane graph in terms of oriented circuits in its medial graph.
△ Less
Submitted 24 February, 2012; v1 submitted 21 June, 2011;
originally announced June 2011.
-
Partial duals of plane graphs, separability and the graphs of knots
Authors:
Iain Moffatt
Abstract:
There is a well-known way to describe a link diagram as a (signed) plane graph, called its Tait graph. This concept was recently extended, providing a way to associate a set of embedded graphs (or ribbon graphs) to a link diagram. While every plane graph arises as a Tait graph of a unique link diagram, not every embedded graph represents a link diagram. Furthermore, although a Tait graph describes…
▽ More
There is a well-known way to describe a link diagram as a (signed) plane graph, called its Tait graph. This concept was recently extended, providing a way to associate a set of embedded graphs (or ribbon graphs) to a link diagram. While every plane graph arises as a Tait graph of a unique link diagram, not every embedded graph represents a link diagram. Furthermore, although a Tait graph describes a unique link diagram, the same embedded graph can represent many different link diagrams. One is then led to ask which embedded graphs represent link diagrams, and how link diagrams presented by the same embedded graphs are related to one another. Here we answer these questions by characterizing the class of embedded graphs that represent link diagrams, and then using this characterization to find a move that relates all of the link diagrams that are presented by the same set of embedded graphs.
△ Less
Submitted 28 February, 2012; v1 submitted 23 July, 2010;
originally announced July 2010.
-
The Tutte-Potts connection in the presence of an external magnetic field
Authors:
Joanna A. Ellis-Monaghan,
Iain Moffatt
Abstract:
The classical relationship between the Tutte polynomial of graph theory and the Potts model of statistical mechanics has resulted in valuable interactions between the disciplines. Unfortunately, it does not include the external magnetic fields that appear in most Potts model applications. Here we define the V-polynomial, which lifts the classical relationship between the Tutte polynomial and the z…
▽ More
The classical relationship between the Tutte polynomial of graph theory and the Potts model of statistical mechanics has resulted in valuable interactions between the disciplines. Unfortunately, it does not include the external magnetic fields that appear in most Potts model applications. Here we define the V-polynomial, which lifts the classical relationship between the Tutte polynomial and the zero field Potts model to encompass external magnetic fields. The V-polynomial generalizes Nobel and Welsh's W-polynomial, which extends the Tutte polynomial by incorporating vertex weights and adapting contraction to accommodate them. We prove that the variable field Potts model partition function (with its many specializations) is an evaluation of the V-polynomial, and hence a polynomial with deletion-contraction reduction and Fortuin-Kasteleyn type representation. This unifies an important segment of Potts model theory and brings previously successful combinatorial machinery, including complexity results, to bear on a wider range of statistical mechanics models.
△ Less
Submitted 15 February, 2011; v1 submitted 29 May, 2010;
originally announced May 2010.
-
Twisted duality for embedded graphs
Authors:
Joanna A. Ellis-Monaghan,
Iain Moffatt
Abstract:
We consider two operations on an edge of an embedded graph (or equivalently a ribbon graph): giving a half-twist to the edge and taking the partial dual with respect to the edge. These two operations give rise to an action of S_3^{|E(G)|}, the ribbon group, on G. The action of the ribbon group on embedded graphs extends the concepts of duality, partial duality and Petrie duality. We show that this…
▽ More
We consider two operations on an edge of an embedded graph (or equivalently a ribbon graph): giving a half-twist to the edge and taking the partial dual with respect to the edge. These two operations give rise to an action of S_3^{|E(G)|}, the ribbon group, on G. The action of the ribbon group on embedded graphs extends the concepts of duality, partial duality and Petrie duality. We show that this ribbon group action gives a complete characterization of duality in that if G is any cellularly embedded graph with medial graph G_m, then the orbit of G under the group action is precisely the set of all graphs with medial graphs isomorphic (as abstract graphs) to G_m. We provide characterizations of special sets of twisted duals, such as the partial duals, of embedded graphs in terms of medial graphs and we show how different kinds of graph isomorphism give rise to these various notions of duality. The ribbon group action then leads to a deeper understanding of the properties of, and relationships among, various graph polynomials via the generalized transition polynomial which interacts naturally with the ribbon group action.
△ Less
Submitted 27 December, 2010; v1 submitted 30 June, 2009;
originally announced June 2009.
-
A characterization of partially dual graphs
Authors:
Iain Moffatt
Abstract:
In this paper, we extend the recently introduced concept of partially dual ribbon graphs to graphs. We then go on to characterize partial duality of graphs in terms of bijections between edge sets of corresponding graphs. This result generalizes a well known result of J. Edmonds in which natural duality of graphs is characterized in terms of edge correspondence, and gives a combinatorial charact…
▽ More
In this paper, we extend the recently introduced concept of partially dual ribbon graphs to graphs. We then go on to characterize partial duality of graphs in terms of bijections between edge sets of corresponding graphs. This result generalizes a well known result of J. Edmonds in which natural duality of graphs is characterized in terms of edge correspondence, and gives a combinatorial characterization of partial duality.
△ Less
Submitted 19 April, 2010; v1 submitted 13 January, 2009;
originally announced January 2009.
-
Partial duality and Bollobas and Riordan's ribbon graph polynomial
Authors:
Iain Moffatt
Abstract:
Recently S. Chmutov introduced a generalization of the dual of a ribbon (or embedded) graph and proved a relation between Bollobas and Riordan's ribbon graph polynomial of a ribbon graph and its generalized duals. Here I show that the duality relation satisfied by the ribbon graph polynomial can be understood in terms of knot theory and I give a simple proof of the relation via the homfly polyno…
▽ More
Recently S. Chmutov introduced a generalization of the dual of a ribbon (or embedded) graph and proved a relation between Bollobas and Riordan's ribbon graph polynomial of a ribbon graph and its generalized duals. Here I show that the duality relation satisfied by the ribbon graph polynomial can be understood in terms of knot theory and I give a simple proof of the relation via the homfly polynomial of a knot.
△ Less
Submitted 24 August, 2009; v1 submitted 17 September, 2008;
originally announced September 2008.
-
Expansions for the Bollobas-Riordan polynomial of separable ribbon graphs
Authors:
Stephen Huggett,
Iain Moffatt
Abstract:
We define 2-decompositions of ribbon graphs, which generalise 2-sums and tensor products of graphs. We give formulae for the Bollobas-Riordan polynomial of such a 2-decomposition, and derive the classical Brylawski formula for the Tutte polynomial of a tensor product as a (very) special case. This study was initially motivated from knot theory, and we include an application of our formulae to mu…
▽ More
We define 2-decompositions of ribbon graphs, which generalise 2-sums and tensor products of graphs. We give formulae for the Bollobas-Riordan polynomial of such a 2-decomposition, and derive the classical Brylawski formula for the Tutte polynomial of a tensor product as a (very) special case. This study was initially motivated from knot theory, and we include an application of our formulae to mutation in knot diagrams.
△ Less
Submitted 27 May, 2009; v1 submitted 23 October, 2007;
originally announced October 2007.
-
Unsigned state models for the Jones polynomial
Authors:
Iain Moffatt
Abstract:
It is well a known and fundamental result that the Jones polynomial can be expressed as Potts and vertex partition functions of signed plane graphs. Here we consider constructions of the Jones polynomial as state models of unsigned graphs and show that the Jones polynomial of any link can be expressed as a vertex model of an unsigned embedded graph.
In the process of deriving this result, we s…
▽ More
It is well a known and fundamental result that the Jones polynomial can be expressed as Potts and vertex partition functions of signed plane graphs. Here we consider constructions of the Jones polynomial as state models of unsigned graphs and show that the Jones polynomial of any link can be expressed as a vertex model of an unsigned embedded graph.
In the process of deriving this result, we show that for every diagram of a link in the 3-sphere there exists a diagram of an alternating link in a thickened surface (and an alternating virtual link) with the same Kauffman bracket. We also recover two recent results in the literature relating the Jones and Bollobas-Riordan polynomials and show they arise from two different interpretations of the same embedded graph.
△ Less
Submitted 28 April, 2009; v1 submitted 22 October, 2007;
originally announced October 2007.
-
A permanent formula for the Jones polynomial
Authors:
Martin Loebl,
Iain Moffatt
Abstract:
The permanent of a square matrix is defined in a way similar to the determinant, but without using signs. The exact computation of the permanent is hard, but there are Monte-Carlo algorithms that can estimate general permanents. Given a planar diagram of a link L with $n$ crossings, we define a 7n by 7n matrix whose permanent equals to the Jones polynomial of L. This result accompanied with recent…
▽ More
The permanent of a square matrix is defined in a way similar to the determinant, but without using signs. The exact computation of the permanent is hard, but there are Monte-Carlo algorithms that can estimate general permanents. Given a planar diagram of a link L with $n$ crossings, we define a 7n by 7n matrix whose permanent equals to the Jones polynomial of L. This result accompanied with recent work of Freedman, Kitaev, Larson and Wang provides a Monte-Carlo algorithm to any decision problem belonging to the class BQP, i.e. such that it can be computed with bounded error in polynomial time using quantum resources.
△ Less
Submitted 11 February, 2011; v1 submitted 31 May, 2007;
originally announced May 2007.
-
On the HOMFLY and Tutte polynomials
Authors:
Iain Moffatt
Abstract:
A celebrated result of F. Jaeger states that the Tutte polynomial of a planar graph is determined by the HOMFLY polynomial of an associated link. Here we are interested in the converse of this result. We consider the question `to what extent does the Tutte polynomial determine the HOMFLY polynomial of any knot?' We show that the HOMFLY polynomial of a knot is determined by Tutte polynomials of p…
▽ More
A celebrated result of F. Jaeger states that the Tutte polynomial of a planar graph is determined by the HOMFLY polynomial of an associated link. Here we are interested in the converse of this result. We consider the question `to what extent does the Tutte polynomial determine the HOMFLY polynomial of any knot?' We show that the HOMFLY polynomial of a knot is determined by Tutte polynomials of plane graphs associated to the knot.
△ Less
Submitted 30 June, 2008; v1 submitted 4 April, 2007;
originally announced April 2007.
-
Knot invariants and the Bollobas-Riordan polynomial of embedded graphs
Authors:
Iain Moffatt
Abstract:
For a graph G embedded in an orientable surface Σ, we consider associated links L(G) in the thickened surface Σ\times I. We relate the HOMFLY polynomial of L(G) to the recently defined Bollobas-Riordan polynomial of a ribbon graph. This generalizes celebrated results of Jaeger and Traldi. We use knot theory to prove results about graph polynomials and, after discussing questions of equivalence o…
▽ More
For a graph G embedded in an orientable surface Σ, we consider associated links L(G) in the thickened surface Σ\times I. We relate the HOMFLY polynomial of L(G) to the recently defined Bollobas-Riordan polynomial of a ribbon graph. This generalizes celebrated results of Jaeger and Traldi. We use knot theory to prove results about graph polynomials and, after discussing questions of equivalence of the polynomials, we go on to use our formulae to prove a duality relation for the Bollobas-Riordan polynomial. We then consider the specialization to the Jones polynomial and recent results of Chmutov and Pak to relate the Bollobas-Riordan polynomials of an embedded graph and its tensor product with a cycle.
△ Less
Submitted 16 December, 2006; v1 submitted 17 May, 2006;
originally announced May 2006.
-
A new proof that alternating links are non-trivial
Authors:
Iain Moffatt
Abstract:
We use a simple geometric argument and small cancellation properties of link groups to prove that alternating links are non-trivial. This proof uses only classic results in topology and combinatorial group theory.
We use a simple geometric argument and small cancellation properties of link groups to prove that alternating links are non-trivial. This proof uses only classic results in topology and combinatorial group theory.
△ Less
Submitted 26 September, 2008; v1 submitted 11 January, 2006;
originally announced January 2006.
-
The chromatic polynomial of fatgraphs and its categorification
Authors:
Martin Loebl,
Iain Moffatt
Abstract:
Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov homology of an associated link. We apply this connection with Khovanov homology…
▽ More
Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov homology of an associated link. We apply this connection with Khovanov homology to show that the torsion-free part of our chromatic homology is independent of the choice of planar embedding of a graph.
We extend our construction and categorify the Bollobas-Riordan polynomial (a generalisation of the Tutte polynomial to embedded graphs). We prove that both our chromatic homology and the Khovanov homology of an associated link can be recovered from this categorification.
△ Less
Submitted 28 November, 2007; v1 submitted 22 November, 2005;
originally announced November 2005.
-
On the group-like behaviour of the Le-Murakami-Ohtsuki invariant
Authors:
David M. Jackson,
Iain Moffatt,
Alejandro Morales
Abstract:
We study the effect of Feynman integration and diagrammatic differential operators on the structure of group-like elements in the algebra generated by coloured vertex-oriented uni-trivalent graphs. We provide applications of our results to the study of the LMO invariant, a quantum invariant of manifolds. We also indicate further situations in which our results apply and may prove useful. The enu…
▽ More
We study the effect of Feynman integration and diagrammatic differential operators on the structure of group-like elements in the algebra generated by coloured vertex-oriented uni-trivalent graphs. We provide applications of our results to the study of the LMO invariant, a quantum invariant of manifolds. We also indicate further situations in which our results apply and may prove useful. The enumerative approach that we adopt has a clarity that has enabled us to perceive a number of generalizations.
△ Less
Submitted 31 March, 2006; v1 submitted 17 November, 2005;
originally announced November 2005.
-
The Aarhus integral and the mu-invariants
Authors:
Iain Moffatt
Abstract:
We relate the tree part of the Aarhus integral to Milnor's mu-invariants of string-links in homology balls thus generalizing results of Habegger and Masbaum.
We relate the tree part of the Aarhus integral to Milnor's mu-invariants of string-links in homology balls thus generalizing results of Habegger and Masbaum.
△ Less
Submitted 17 November, 2005;
originally announced November 2005.
-
Integration and conjugacy in knot theory
Authors:
Iain Moffatt
Abstract:
This thesis consists of three self-contained chapters. The first two concern quantum invariants of links and three manifolds and the third contains results on the word problem for link groups.
In chapter 1 we relate the tree part of the Aarhus integral to the mu-invariants of string-links in homology balls thus generalizing results of Habegger and Masbaum.
There is a folklore result in physi…
▽ More
This thesis consists of three self-contained chapters. The first two concern quantum invariants of links and three manifolds and the third contains results on the word problem for link groups.
In chapter 1 we relate the tree part of the Aarhus integral to the mu-invariants of string-links in homology balls thus generalizing results of Habegger and Masbaum.
There is a folklore result in physics saying that the Feynman integration of an exponential is itself an exponential. In chapter 2 we state and prove an exact formulation of this statement in the language which is used in the theory of finite type invariants.
The final chapter is concerned with properties of link groups. In particular we study the relationship between known solutions from small cancellation theory and normal surface theory for the word and conjugacy problems of the groups of (prime) alternating links. We show that two of the algorithms in the literature for solving the word problem, each using one of the two approaches, are the same. Then, by considering small cancellation methods, we give a normal surface solution to the conjugacy problem of these link groups and characterize the conjugacy classes. Finally as an application of the small cancellation properties of link groups we give a new proof that alternating links are non-trivial.
△ Less
Submitted 17 November, 2005;
originally announced November 2005.