Handbook of the Tutte Polynomial and Related Topics

Cover
Half Title
Title Page
Copyright Page
Contents
Preface
Contributors
I. Fundamentals
1. Graph theory
1.1. Introduction
1.2. Graph theory conventions
2. The Tutte polynomial for graphs
2.1. Introduction
2.2. The standard definitions of the Tutte polynomial
2.3. Multiplicativity
2.4. Universality of the Tutte polynomial
2.5. Duality
3. Essential properties of the Tutte polynomial
3.1. Introduction
3.2. Evaluations at special points
3.3. Coefficient properties and irreducibility
3.4. Evaluations along curves
3.5. Dual graphs and medial graphs
3.6. Knots
3.7. Signed, colored and topological Tutte polynomials
3.8. Open problems
4. Matroid theory
4.1. Introduction
4.2. Fundamental examples and definitions
4.3. The many faces of a matroid
4.4. Duality
4.5. Basic constructions
4.6. More examples
4.7. The Tutte polynomial of a matroid
4.8. Some particular evaluations
4.9. Some basic identities
5. Tutte polynomial activities
5.1. Introduction
5.2. Activities for maximal spanning forests
5.3. Activity bipartition
5.4. Activities for subgraphs
5.5. Depth-first search external activity
5.6. Activities via combinatorial maps
5.7. Unified activities for subgraphs via decision trees
5.8. Orientation activities
5.9. Active orders
5.10. Shellability and activity
5.11. Open problems
6. Tutte uniqueness and Tutte equivalence
6.1. Introduction
6.2. Basic notions and results, and initial examples
6.3. Tutte uniqueness and equivalence for graphs
6.4. Tutte uniqueness and equivalence for matroids
6.5. Related results
6.6. Open problems
II. Computation
7. Computational techniques
7.1. Introduction
7.2. Direct computation
7.3. Duality and matroid operations
7.4. Using equivalent polynomials
7.5. Transfer matrix method
7.6. Decomposition
7.7. Counting arguments
7.8. Other strategies
7.9. Computation for common graphs and matroids
7.10. Open problems
8. Computational resources
8.1. Introduction
8.2. Implementations
8.3. Comparative performance
8.4. Conclusions
8.5. Open problems
9. The exact complexity of the Tutte polynomial
9.1. Introduction
9.2. Complexity classes and graph width
9.3. Exact evaluations on graphs
9.4. Exact evaluation on matroids
9.5. Algebraic models of computation
9.6. Open problems
10. Approximating the Tutte polynomial
10.1. Introduction
10.2. Notation
10.3. Randomized approximation schemes
10.4. Positive approximation results
10.5. Negative results: inapproximability
10.6. The quantum connection
10.7. Open problems
III. Specializations
11. Foundations of the chromatic polynomial
11.1. Introduction
11.2. Computing chromatic polynomials
11.3. Properties of chromatic polynomials
11.4. Chromatically equivalent graphs
11.5. Roots of chromatic polynomials
11.6. Open problems
12. Flows and colorings
12.1. Introduction
12.2. Flows and the flow polynomial
12.3. Coloring-
flow convolution formulas
12.4. A-bicycles
12.5. Open problems
13. Skein polynomials and the Tutte polynomial when x = y
13.1. Introduction
13.2. Vertex states, graph states, and skein relations
13.3. Skein polynomials
13.4. Evaluations of the Tutte polynomial along x = y
13.5. Open problems
14. The interlace polynomial and the Tutte—Martin polynomial
14.1. Introduction
14.2. Notation
14.3. Interlace polynomial
14.4. Martin polynomial
14.5. Global interlace polynomial
14.6. Two-variable interlace polynomial
14.7. Weighted interlace polynomial
14.8. Connection with the Tutte polynomial
14.9. Isotropic systems and the Tutte‒Martin polynomial
14.10. Interlace polynomials for delta-matroids
14.11. Summary
14.12. Open problems
IV. Applications
15. Network reliability
15.1. Introduction
15.2. Forms of the reliability polynomial
15.3. Calculating coefficients
15.4. Transformations
15.5. Coefficient inequalities
15.6. Analytic properties of reliability
15.7. Open problems
16. Codes
16.1. Introduction
16.2. Linear codes and the Tutte polynomial
16.3. Ordered tuples and subcodes
16.4. Equivalence of the Tutte polynomial and weights
16.5. Orbital polynomials
16.6. Other generalizations and applications
16.7. Wei's duality theorem
16.8. Open problems
17. The chip-firing game and the sandpile model
17.1. Introduction
17.2. The Tutte polynomial and the chip-firing game
17.3. Sandpile models
17.4. The critical group and parking functions
17.5. Open problems
18. The Tutte polynomial and knot theory
18.1. Introduction
18.2. Graphs and links
18.3. Polynomial invariants of links
18.4. The Tutte and Jones polynomials
18.5. The Tutte and HOMFLYPT polynomials
18.6. Applications in knot theory
18.7. The Bollobás–Riordan polynomial
18.8. Categorification
18.9. Open problems
19. Quantum field theory connections
19.1. Introduction
19.2. The Symanzik polynomials as evaluations of the multivariate Tutte polynomial
19.3. The Symanzik polynomials in quantum field theory
19.4. Hopf algebras and the Tutte polynomial
19.5. Open problems
20. The Potts and random-cluster models
20.1. Introduction
20.2. Probabilistic models from physics
20.3. Phase transition
20.4. Basic properties of random-cluster measures
20.5. The Limit as q ↓ 0
20.6. Flow polynomial
20.7. The limit of zero temperature
20.8. The random-cluster model on the complete graph
20.9. Open problems
21. Where Tutte and Holant meet: a view from counting complexity
21.1. Introduction
21.2. Definition of Holant and related concepts
21.3. Specializations of the Tutte polynomial with local expressions
21.4. Open problems
22. Polynomials and graph homomorphisms
22.1. Introduction
22.2. Homomorphism profiles
22.3. Edge coloring models
22.4. Connection matrices
22.5. Matroid invariants
22.6. Graph polynomials from homomorphism profiles
22.7. Graph polynomials by recurrence formulas
22.8. Open problems
V. Extensions
23. Digraph analogues of the Tutte polynomial
23.1. Introduction
23.2. The cover polynomial
23.3. Tutte invariants for alternating dimaps
23.4. Gordon‒Traldi polynomials
23.5. The B-polynomial
23.6. Open problems
24. Multivariable, parameterized, and colored extensions of the Tutte polynomial
24.1. Introduction
24.2. Parameterized and multivariate Tutte polynomials
24.3. Identities for parameterized Tutte polynomials
24.4. Related parameterized polynomials
24.5. Four parameters: colored and strong extensions
24.6. Ported polynomials, and others
24.7. Open problems
25. Zeros of the Tutte polynomial
25.1. Introduction
25.2. The multivariate Tutte polynomial
25.3. Zero-free regions in R2
25.4. Density of real zeros
25.5. Determining the sign of the Tutte polynomial
25.6. Complex zeros
25.7. Open problems
26. The U, V and W polynomials
26.1. Introduction
26.2. Properties of the polynomials
26.3. Equivalent polynomials and symmetric functions
26.4. Graphs determined by their U-polynomial
26.5. Complexity issues
26.6. Related polynomials
26.7. Open problems
27. Topological extensions of the Tutte polynomial
27.1. Introduction
27.2. Ribbon graphs.
27.3. The Bollobás‒Riordan polynomial.
27.4. The Las Vergnas polynomial.
27.5. The Krushkal polynomial.
27.6. Polynomials from deletion‒contraction relations
27.7. Polynomials arising from flows and tensions
27.8. Quasi-trees
27.9. Open problems
28. The Tutte polynomial of matroid perspectives
28.1. Introduction
28.2. Matroid perspectives
28.3. The Tutte polynomial of a matroid perspective
28.4. Deletion–contraction, convolution, and the Möbius function
28.5. Subset activities in matroids and perspectives
28.6. Five-variable expansion and partial derivatives
28.7. Representable and binary cases
28.8. Brief accounts of related polynomials
28.9. Open problems
29. Hyperplane arrangements and the finite field method
29.1. Introduction
29.2. Hyperplane arrangements
29.3. Polynomial invariants
29.4. Topological and algebraic invariants
29.5. The finite field method
29.6. A catalog of characteristic and Tutte polynomials
29.7. Multivariate and arithmetic Tutte polynomials
29.8. Open problems
30. Some algebraic structures related to the Tutte polynomial
30.1. Introduction
30.2. Orlik‒Solomon algebras
30.3. Coalgebras associated with matroids
30.4. Open problems
31. The Tutte polynomial of oriented matroids
31.1. Introduction
31.2. Oriented matroids and related structures
31.3. Tutte polynomial in terms of orientation-activities
31.4. Counting bounded regions and bipolar orientations
31.5. Generalizations to oriented matroid perspectives
31.6. Activity classes and active partitions
31.7. Filtrations in matroids and B-invariants of minors
31.8. The active basis and the canonical active bijection
31.9. Reorientations/subsets bijection, refined orientation-activities
31.10. Counting circuit/cocircuit reversal classes
31.11. Open problems
32. Valuative invariants on matroid basis polytopes
32.1. Introduction
32.2. Valuative functions on matroid base polytopes
32.3. Open problems
33. Non-matroidal generalizations
33.1. Introduction
33.2. Greedoids and the Tutte polynomial
33.3. Antimatroids
33.4. The B-invariant
33.5. Open problems
VI. History
34. The history of Tutte‒Whitney polynomials
34.1. Introduction
34.2. The classic papers
34.3. Preliminaries
34.4. Notation in the papers
34.5. Whitney, 1932: A logical expansion in mathematics
34.6. Whitney, 1932: The coloring of graphs
34.7. Whitney, 1933: Topological invariants for graphs
34.8. Tutte, 1947: A ring in graph theory
34.9. Tutte's PhD thesis
34.10. Tutte, 1954: A contribution to the theory of chromatic polynomials
34.11. Tutte, 1967: On dichromatic polynomials
34.12. Potts, 1952: Some generalized order-disorder transformations
34.13. Zykov
34.14. Some other work
34.15. Closing remarks
Acknowledgments
Bibliography
Selected evaluations and interpretations
Symbols
Index