PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized duality for graphs on surfaces and the signed Bollobas-Riordan polynomial

Sergei Chmutov

arXiv:0711.3490v3math.COmath.GT

TL;DR

The paper generalizes duality for surface-embedded graphs to duality relative to an edge subset, potentially changing the embedding surface. It proves a signed Bollobás–Riordan polynomial relation under this duality and uses it to connect earlier Jones-polynomial specializations.

  • Problem

    The paper addresses how to extend natural graph duality on surfaces from all edges to an arbitrary subset of edges.

  • Method

    It constructs generalized dual ribbon graphs from spanning subgraphs and proves invariance of a restricted signed Bollobás–Riordan polynomial under generalized duality.

  • Results

    The relation unifies prior duality results and supports expressing the Kauffman bracket and Jones polynomial through Bollobás–Riordan polynomial specializations.

  • Takeaways & Limitations

    The framework provides a common derivation of several earlier link-theoretic theorems, including results for virtual and classical links.

  • Takeaways & Limitations

    The diagram quantity [L] used in the link application is not a topological link invariant, although it determines the Jones polynomial by substitution.

Abstract

from arXiv · show

We generalize the natural duality of graphs embedded into a surface to a duality with respect to a subset of edges. The dual graph might be embedded into a different surface. We prove a relation between the signed Bollobas-Riordan polynomials of dual graphs. This relation unifies various recent results expressing the Jones polynomial of links as specializations of the Bollobas-Riordan polynomials.

Introduction

The paper extends surface-embedded graph duality to duality relative to an edge subset and relates the resulting signed Bollobás–Riordan polynomials. This framework unifies prior polynomial and link-theoretic results.

  • Ribbon graphs: Ribbon graphs formalize cellularly embedded graphs as surfaces with boundary decomposed into vertex and edge discs.Shrinking discs recovers the underlying graph embedded in a closed surface.
  • Natural duality: The natural Euler–Poincaré dual is formed by filling boundary components with faces, replacing original vertices by these faces, and retaining the edge discs with changed attachments.The original and dual underlying graphs are naturally embedded in the same closed surface, with vertices and faces interchanged.
  • Generalized duality: For a signed ribbon graph and edge subset E′, the generalized dual uses the spanning subgraph on E′, turns its boundary components into dual vertices, and reverses the signs of edges in E′.The generalized dual need not have the same genus as the original graph.
  • Polynomial relation: The paper proves a duality relation for the signed Bollobás–Riordan polynomial of G and its generalized dual, recovering ordinary polynomial duality and planar Tutte duality in special cases.When E′ is the full edge set and all edges are positive, the relation specializes to earlier Bollobás–Riordan results; for planar G it becomes Tutte duality.
  • Link applications: The generalized duality also provides a common route to earlier results connecting Bollobás–Riordan polynomial specializations with the Jones polynomial of links.The paper derives the theorems of [DFKLS] and [CP] from the result of.

1. Ribbon graphs and generalized duality

The paper develops ribbon graphs, their arrow presentations, and duality with respect to edge subsets. It establishes algebraic and topological properties of this generalized duality, including its interaction with contraction and deletion.

  • Definitions: A ribbon graph is a surface with boundary decomposed into vertex and edge discs satisfying prescribed intersection conditions, and a signed ribbon graph assigns each edge a sign in {±1}.Ribbon graphs are considered up to homeomorphisms preserving the vertex–edge decomposition.
  • Arrow presentations: Arrow presentations encode ribbon graphs using oriented circles and paired labeled arrows, with equivalences corresponding to reversing vertex or edge orientations.The signs of edges are recorded separately for signed ribbon graphs.
  • Generalized dual construction: For E′⊆E(G), the generalized dual G^E′ is built from boundary components of the spanning subgraph on E′, while edges in E′ receive changed attachments and opposite signs.The same construction can be described geometrically by doubling selected edge ribbons and using the resulting boundary components as dual vertices.
  • Properties: Generalized duality composes by symmetric difference, preserves orientability and connected-component count, and satisfies G^{E(G)}=G*; for planar graphs this is ordinary planar duality.These properties make repeated dualization an action of a product of two-element groups on ribbon graphs.
  • Contraction and deletion: The generalized duality extends contraction–deletion: for e∉E′, dualizing after contraction or deletion corresponds to changing the dual edge operation and the selected subset.Specifically, (G/e)^E′=G^{E′∪e}−e=G^E′/e and (G−e)^E′=G^{E′∪e}/e=G^E′−e.

2. The Bollob´as-Riordan polynomial

This section defines the signed Bollobás–Riordan polynomial and develops its multiplicative, sign-change, and contraction–deletion properties. These identities support the later duality theorem, including a specialization handling nontrivial orientable loops.

  • Definition: The signed Bollobás–Riordan polynomial sums contributions over spanning subgraphs using vertex, rank, nullity, boundary-component, and sign-related parameters.It is generally a Laurent polynomial in x^1/2, y^1/2, and z.
  • Relation to Tutte theory: The polynomial generalizes the Tutte polynomial to surface-embedded graphs, while z=1 yields the signed Tutte polynomial of the underlying graph.For unsigned graphs, it connects to the original Bollobás–Riordan polynomial by substitution.
  • Example: For the example considered, the polynomial is RG(x,y,z)=x+2+y+xyz^2+2yz+y^2z.The example enumerates spanning subgraphs and their associated graph parameters.
  • Operations: The polynomial is multiplicative under disjoint union and one-point join, with one-point-join ambiguity not detected by the polynomial.The signed case follows from additivity of the sign-related parameter.
  • Contraction–deletion: For positive ordinary edges and bridges, contraction–deletion gives RG=RG/e+RG−e and RG=(x+1)RG/e, while negative edges receive corresponding x- and y-dependent factors.The identities follow by partitioning spanning subgraphs according to whether they contain the edge.
  • Loop cases: Specialized formulas also cover trivial orientable and non-orientable loops, while nontrivial orientable loops require the main theorem’s restriction to xyz^2=1.For non-orientable positive loops, one formula is RG=RG−e+yzRG/e.

3. Main result

The main theorem states that a normalized signed Bollobás–Riordan polynomial is invariant under duality with respect to any chosen edge subset. Its proof uses a bijection between spanning subgraphs and contraction–deletion relations, including signed loop cases.

  • Theorem 3.1: For any edge subset E′, the normalized polynomial x^k(G)y^v(G)z^(v(G)+1)R_G restricted to xyz^2=1 is invariant under generalized duality.When half-integer exponents occur, the restriction is interpreted on x^1/2y^1/2z=1.
  • Proof strategy: The proof maps each spanning subgraph F of G bijectively to a spanning subgraph F′ of the dual graph by reversing membership for edges in E′.Edges in E′ are included in F′ exactly when absent from F; other edges preserve membership.
  • Proof strategy: The spanning-subgraph correspondence preserves faces while relating edge counts and signed contributions through a factor x^1/2y^1/2z.The sign-dependent calculation gives the same correction factor whether the selected edge is positive or negative.
  • Proof strategy: By reducing generalized duality to a single-edge operation, the proof invokes contraction–deletion and exchanges deletion with contraction under duality.The argument assumes the edge lies in F without loss of generality, then uses G^{\{e\}}−e=G/e and G^{\{e\}}/e=G−e.
  • Signed loop cases: The signed nontrivial-loop cases follow because duality changes a loop into an ordinary edge and reverses its sign.The two sign cases use the corresponding contraction–deletion equations and yield the stated relations after substituting x^1/2y^1/2z=1.

4. Natural duality of graphs on surfaces

For the full edge set, generalized duality yields the natural dual of a signed ribbon graph and a duality relation for its Bollobás–Riordan polynomial. The result extends earlier orientable, unsigned cases and specializes to planar Tutte duality.

  • Natural duality: The duality with respect to all edges produces the natural dual signed graph, embedded in the same surface as the original graph in a naturally dual manner.The underlying ribbon graph is unchanged when the dual sign function is changed back to the original sign function.
  • Natural duality: The proposition uses g=k(G)−χ(eG)/2, which equals the surface genus in the orientable case, to express the natural-duality relation.The proof derives the exponent through component, vertex, edge, and Euler-characteristic identities.
  • Scope extension: The result extends previous proofs from unsigned orientable ribbon graphs to signed graphs that are not necessarily orientable.Earlier work covered unsigned orientable graphs, while the paper establishes the proposition in the broader signed, potentially non-orientable setting.
  • Planar specialization: In the planar connected case, the Bollobás–Riordan polynomial specializes to the Tutte polynomial, and generalized duality gives T_Γ(x,y)=T_Γ∗(y,x).The planar parameter g is zero, so the famous planar Tutte duality follows directly from the Bollobás–Riordan relation.

5. Virtual links and the Jones polynomial

The paper adopts the Kauffman framework for virtual links, representing link states by A- and B-splittings at classical crossings. The Kauffman bracket depends on the diagram, while a writhe correction yields the Jones polynomial, and the framework supports Bollobás–Riordan specializations.

  • Virtual links: Virtual link diagrams treat virtual crossings as defects of planar figures rather than genuine crossings, and virtual crossings do not connect components.The framework includes classical and virtual Reidemeister moves.
  • Kauffman states: A state chooses an A- or B-splitting at every classical crossing, giving 2^n states for a diagram with n crossings.The A- and B-splittings join different pairs of vertical angles at each classical crossing.
  • Kauffman bracket: The Kauffman bracket is defined as a polynomial in A, B, and d from the state expansion of a virtual link diagram.The state data include the numbers of A- and B-splittings and the number of resulting curve components.
  • Jones polynomial: The Kauffman bracket depends on the link diagram rather than being a topological invariant, whereas the Jones polynomial is a topological invariant obtained by a substitution with a writhe correction.The writhe is determined from an orientation by summing the signs of classical crossings.
  • Virtual links: The paper applies the same Kauffman-bracket construction to virtual links and illustrates the resulting bracket and Jones polynomials for example virtual knots.Virtual crossings are distinguished in figures from classical crossings.

6. Thistlethwaite’s type theorems

The paper generalizes Thistlethwaite-type results to virtual links by associating signed ribbon graphs with link states and using generalized duality to show state-independent Bollobás–Riordan specializations. This framework derives earlier results for classical and checkerboard-colorable links from a common theorem.

  • Virtual-link construction: Virtual link states are converted into possibly non-orientable signed ribbon graphs by representing state circles as vertices and crossings as signed edge-bands.A-splittings receive positive signs and B-splittings negative signs.
  • State independence: The Kauffman bracket, and hence the Jones polynomial, is expressed as a specialization of the Bollobás–Riordan polynomial of a state-associated ribbon graph.The generalized duality theorem makes the resulting specialization independent of the initial state.
  • Generalized duality: For two states of the same diagram, the associated ribbon graphs are dual with respect to the edges corresponding to crossings resolved differently.This connects changes of state directly to the paper’s generalized duality operation.
  • State independence: The number of boundary components of a spanning subgraph corresponds to the number of state circles in the associated link state.This correspondence supports a direct relation between link-state expansions and ribbon-graph polynomial expansions.
  • Classical links: The framework recovers the theorem of [DFKLS] for connected classical links by choosing the all-A state, whose graph is orientable and has only positive edges.In this setting, the result is identified as a special case of the paper’s virtual-link theorem.
  • Checkerboard-colorable links: The theorem of [CP] for checkerboard-colorable virtual links follows from the theorem of [CV] through the generalized duality theorem.The paper thereby unifies the constructions and substitutions used in the earlier Thistlethwaite-type results.

7. Possible further directions

The paper identifies several directions for extending generalized duality and understanding its interaction with embedded-graph invariants and Bollobás–Riordan specializations. These include embedding-density parameters, combinatorial interpretations, higher-genus self-duality, and multivariable extensions.

  • Higher-genus self-duality: The paper leaves open whether known constructions classify all self-dual ribbon graphs in higher genera.This question extends existing results concerning spherical self-dual polyhedra and ribbon graphs.
  • Embedding parameters: The behavior of edge-width, face-width, and dual-width under generalized duality remains to be explored.These parameters measure different aspects of embedding density in a closed surface.
  • Characterizing generalized duality: A comparable incidence-based condition for generalized duality with respect to a subset of edges remains an open problem.The existing condition applies to abstract graphs embedded in the same surface under a full edge bijection.
  • Combinatorial interpretations: The paper suggests seeking direct combinatorial bijections for Bollobás–Riordan specializations and additional combinatorial interpretations.One cited specialization, RG(k, k, 1/k), has a coloring-based interpretation and satisfies xyz^2 = 1.
  • Multivariable extensions: The generalized duality could be extended to the multivariable Bollobás–Riordan polynomial for edge-labeled ribbon graphs.The proposed extension would seek a multivariable analogue of the main duality theorem.
Loading 0711.3490v3…