Source-linked AI summary
Graph polynomials and their applications I: The Tutte polynomial
Joanna Ellis-Monaghan, Criel Merino
TL;DR
The survey asks how graph polynomials can encode combinatorial, algebraic, physical, and computational information, using the Tutte polynomial as its central case. It compares equivalent definitions, applications, specializations, generalizations, and complexity questions, showing the polynomial’s broad unifying role while noting unresolved or limited areas of knowledge.
Problem
Graph-polynomial theory requires methods for defining polynomials, extracting combinatorial and algebraic information, relating variants, and understanding applications and computational complexity.
Method
The survey develops recursive, generating-function, and spanning-tree formulations of the Tutte polynomial and uses them to organize applications, specializations, generalizations, duality, and complexity.
Results
The Tutte polynomial serves as a unifying framework for graph invariants, with applications including specializations, planar duality, orientation counts, and approximation questions.
Takeaways & Limitations
Recognizing an application-driven function as a Tutte-polynomial specialization makes the Tutte polynomial’s established body of knowledge available to that application.
Takeaways & Limitations
The survey notes that little is known about flow-polynomial properties beyond consequences of duality with the chromatic polynomial and work on the 5-flow conjecture.
Abstract
from arXiv · showhide
In this survey of graph polynomials, we emphasize the Tutte polynomial and a selection of closely related graph polynomials. We explore some of the Tutte polynomial's many properties and applications and we use the Tutte polynomial to showcase a variety of principles and techniques for graph polynomials in general. These include several ways in which a graph polynomial may be defined and methods for extracting combinatorial information and algebraic properties from a graph polynomial. We also use the Tutte polynomial to demonstrate how graph polynomials may be both specialized and generalized, and how they can encode information relevant to physical applications. We conclude with a brief discussion of computational complexity considerations.
1 Introduction
The survey uses the Tutte polynomial as a model for graph-polynomial theory because of its rich theory, broad applications, and universality under deletion/contraction. It develops definitions, interpretations, specializations, algebraic properties, and computational considerations.
- Motivation: The Tutte polynomial is a two-variable graph polynomial with a universal property for multiplicative graph invariants admitting deletion/contraction reductions.This connects the polynomial to network models across computer science, engineering, optimization, physics, and biology.
- Contributions: The chapter gives recursive and generating-function formulations and states universality through a recipe theorem.
- Applications: Its evaluations recover colorings, flows, orientations, network reliability, and related graph polynomials as specializations.
- Properties: The survey also examines coefficients, zeros, derivatives, and computational complexity.
2 Preliminary Notions
The preliminary section establishes graph-theoretic terminology, operations, invariants, and planar duality used throughout the Tutte-polynomial development. It emphasizes spanning trees and the correspondence between planar graphs and their duals.
- Basic terminology: The section defines graphs, digraphs, isomorphism, connected components, cycles, trails, circuits, cuts, bridges, loops, and ordinary edges.
- Trees: Trees are connected acyclic graphs, and spanning trees will play a fundamental role in the theory of the Tutte polynomial.Loops occur in no spanning tree, whereas bridges occur in every spanning tree of a connected graph.
- Graph operations: Deletion removes an edge, while contraction identifies its endpoints and removes the edge; both operations commute.
- Invariants: A graph invariant is a function on graphs, and a graph polynomial is an invariant whose image lies in a polynomial ring.
- Planar duality: For planar duals, complementary edge sets correspond to spanning trees, so a planar graph and any plane dual have the same number of spanning trees.
3 Defining the Tutte Polynomial
The Tutte polynomial has several equivalent formulations, including deletion–contraction recursion, rank-nullity generating functions, and spanning-tree expansions. Their interplay supports induction, counting, duality, and coefficient interpretations.
- Equivalent definitions: Equivalent formulations of the Tutte polynomial support different proof techniques, including induction for recursion and Möbius inversion for generating functions.
- Recursive definition: The recursive definition repeatedly deletes or contracts ordinary edges until terminal graphs consisting of forests with loops remain.
- Recursive definition: The recursive computation is well defined because the resulting polynomial is independent of the order in which edges are selected.
- Example: For K4 minus one edge, recursive evaluation gives T(G; x, y) = x3 + 2x2 + x + 2xy + y + y2.
- Generating functions: The generating-function formulation facilitates counting because coefficients encode combinatorial structures through variable exponents.
- Duality: For a planar graph and its dual, the Tutte polynomial satisfies a duality relation obtained from the rank-nullity formulation.
- Spanning-tree expansion: The spanning-tree expansion classifies trees using internal and external activity, whose coefficients are independent of the chosen edge order and non-negative.
4 Universality of the Tutte Polynomial
The universality theorem characterizes graph invariants with multiplicativity and deletion/contraction rules as evaluations of the Tutte polynomial. Related results provide both a recipe for recovery and uniqueness for prescribed parameters.
- T-G invariants: A generalized Tutte–Gröthendieck invariant is multiplicative on disjoint unions and one-point joins and obeys fixed deletion/contraction rules.
- Universality: The Tutte polynomial is essentially the only T-G invariant, since other such invariants are evaluations of it.
- Universality: The recipe theorem specifies how to recover a T-G invariant as an evaluation of the Tutte polynomial.
- Unique extension: For any four elements a, b, x0, y0 in a commutative ring with unity, there is a unique well-defined T-G invariant satisfying the prescribed rules and terminal values.
- Technical condition: When a or b is not a unit, the evaluation formulas are interpreted by expanding first and cancelling before evaluation.
- Proof strategy: The universality and unique-extension results are proved by induction on the number of ordinary edges.
5 Combinatorial Interpretations of Some Evaluations
The section shows how Tutte-polynomial evaluations encode spanning subgraphs, orientations, score vectors, and planar medial-graph structures. These interpretations also connect polynomial evaluations to determinant computations and related graph polynomials.
- Spanning Subgraphs: T(G; 1, 1) equals the number of spanning trees of a connected graph.The rank-nullity expansion shows that surviving subsets are connected and have |V| − 1 edges, hence are spanning trees.
- Spanning Subgraphs: T(G; 2, 1) counts spanning forests, while T(G; 1, 2) counts spanning connected subgraphs.
- Spanning Subgraphs: T(G; 2, 2) equals 2^|E|, the number of possible orientations of G.The evaluation also counts all edge orientations, since each edge can be directed toward either endpoint.
- Spanning Subgraphs: The Laplacian cofactor determinant computes the number of spanning trees in polynomial time, making (1, 1) a tractable Tutte-polynomial evaluation.For a connected graph, the relevant cofactor is denoted L′.
- Orientations and Score Vectors: T(G; 2, 0), T(G; 0, 2), and T(G; 1, 0) count acyclic, totally cyclic, and uniquely sourced acyclic orientations, respectively.
- Orientations and Score Vectors: T(G; 2, 1) also equals the number of score vectors of orientations, while planar diagonal evaluations arise through the Martin polynomial of the directed medial graph.For planar G, m(⃗Gm; x) = T(G; x, x), enabling further interpretations using medial-graph decompositions and colorings.
6 Some Specializations
This section shows how Tutte-polynomial specializations recover diverse graph polynomials and combinatorial quantities, including colorings, flows, sandpile configurations, reliability, and shelling data.
- Overview: Specializations of the Tutte polynomial provide generating functions for combinatorial quantities and numerical graph invariants across multiple applications.The survey emphasizes that recognizing an application-driven function as a specialization makes Tutte-polynomial results available to that application.
- 6.1 The Chromatic Polynomial: The chromatic polynomial counts proper vertex colorings and has recursive deletion–contraction behavior, while its Tutte relation may require a multiplier.For a positive integer λ, χ(G; λ) counts admissible λ-colorings; the section also develops its relation to the Tutte polynomial through a T-G invariant adjustment.
- 6.3 The Flow Polynomial: The flow polynomial counts nowhere-zero flows over finite Abelian groups, and Tutte evaluations encode flow-related graph properties and physical configurations.The section notes that every bridgeless graph has a 6-flow, while for 4-regular graphs T(G; 0, −2) counts ice configurations.
- 6.4 Abelian Sandpile Models: The Tutte polynomial along x = 1 generates critical-configuration data in Abelian sandpile models, yielding identities with spanning trees and acyclic orientations.For connected graphs, the number of critical configurations equals the number of spanning trees, and level-0 configurations equal acyclic orientations with a unique source.
- 6.6 The Shelling Polynomial: The section also connects Tutte coefficients with simplicial-complex face enumerators and h-vectors, including an open pure O-sequence conjecture for one graph-derived complex.The conjecture is established for Δ*(G) but remains open for Δ(G).
- 6.5 The Reliability Polynomial: The reliability polynomial is a Tutte specialization representing the probability that active edges connect every vertex pair, while Tutte evaluations also enumerate simplicial-complex data.The section relates reliability, face enumerators, and shelling polynomials to the line x = 1, and records a pure O-sequence result for one graph complex.
7 Some Properties of the Tutte Polynomial
The section develops how Tutte-polynomial coefficients, evaluations, factorizations, and derivatives encode graph structure, orientations, and related polynomial information. It also illustrates both broad combinatorial interpretations and limits of coefficient conjectures.
- The Beta Invariant: The β invariant is the common coefficient t0,1 = t1,0 in the Tutte polynomial and characterizes series-parallel graphs by β(G) = 1.It is unchanged by inserting parallel or series edges and therefore is shared by homeomorphic graphs.
- The Beta Invariant: 2β(G) counts orientations of a connected graph having a unique source and sink, independently of their relative locations.
- Coefficient Relations: Tutte-polynomial coefficients admit orientation-based interpretations through counts of internally and externally active edges, with tij = oi,j/(2i+j).The orientation counts depend on a chosen linear ordering of the edges.
- Coefficient Relations: The conjecture that Tutte-polynomial coefficients are unimodular or log concave is false, and the counterexample extends to an infinite family by adding parallel edges.
- Zeros and Factorization: Tutte polynomials factor exactly over blocks for loopless connected graphs that are not 2-connected, whereas they are irreducible for 2-connected graphs.
- Convolution and the Tutte Polynomial: The Tutte polynomial can be expressed using chromatic and flow polynomials of graph minors, linking its evaluations to related graph invariants.The relation can be proved by deletion/contraction induction or the spanning-trees expansion.
8 The Complexity of the Tutte Polynomial
The section surveys the computational complexity of Tutte-polynomial evaluation, distinguishing tractable special cases from broad #P-hard regions and noting structural restrictions that enable efficient computation. Approximation is also generally difficult, although bounded-tree-width graphs provide an important tractable setting.
- Exact Evaluation: Evaluating the Tutte polynomial is #P-hard except on a special hyperbola and at specified exceptional points, where evaluation is polynomial-time computable.The exceptional points include (1, 1), (−1, −1), (0, −1), (−1, 0), (i, −i), (−i, i), (j, j2), and (j2, j).
- Planar Graphs: For planar graphs, Pfaffian techniques give a polynomial-time algorithm for evaluating the Tutte polynomial along the special hyperbola.
- Planar Graphs: Even among bipartite planar graphs, Tutte-polynomial evaluation remains #P-hard except at specified polynomial-time points.
- Planar Graphs: For λ ≥3, counting λ-colorings of induced subgraphs of the square lattice is #P-complete.
- Approximation: Under RP ≠ NP, no FPRAS exists for Tutte-polynomial evaluation on essentially all but the first quadrant, implying the same for counting nowhere-zero λ-flows when λ > 2.
- Restricted Graph Classes: Graphs of bounded tree-width make many NP-hard problems tractable, and the Tutte polynomial can be computed in polynomial time in that setting.
9 Conclusion
The conclusion places the Tutte polynomial in a broader mathematical setting and directs readers to foundational references for further study. Although the survey focuses on graphs, matroids are identified as its natural domain.
- Conclusion: The Tutte polynomial is naturally a matroid polynomial, although the survey focuses on graphs to broaden accessibility.
Index
The index lists terms spanning graph structure, flows, orientations, polynomial variants, and Tutte-polynomial properties.
- Graph Concepts: The index covers graph concepts such as bridges, cycles, trees, loops, and cyclomatic number.
- Applications and Structures: It includes flow-related terms such as H-flows and nowhere-zero flows, along with reliability and score-vector terminology.
- Tutte-Polynomial Concepts: It also lists Tutte-polynomial concepts including uniqueness, universality, and Tutte–Gröthendieck invariants.