Handbook of the Tutte Polynomial and Related Topics (Chapman & Hall/Crc Monographs and Research Notes in Mathematics)

Preface The Tutte polynomial is surely the most studied graph polynomial, particularly when all of its many specializations, generalizations, and applications are included. The impact of the Tutte polynomial comes in part from it being a universal invariant. It subsumes graph parameters and invariants that satisfy recursive deletion-contraction relations. Because of this property, the Tutte polynomial appears in various guises throughout mathematics and physics. For example, it encompasses the Potts and Ising models from physics, the Jones and homflypt polynomials from knot theory, the weight enumerator of linear codes, network reliability, the chromatic polynomial, and the many other applications that appear in this handbook.This handbook consists of thirty-four chapters on the Tutte polynomial, its applications, and related topics, each written by experts in the field. Each chapter offers a stand-alone account of some aspect of the Tutte polynomial and is written so as to be accessible to non-experts yet comprehensive enough for experts.The chapters are organized into six parts. Part I describes the fundamental properties of the Tutte polynomial. In particular the first four chapters provide an overview of the Tutte polynomial and the necessary background for the rest of the handbook. Part II is concerned with questions of computation, complexity, and approximation for the Tutte polynomial. Part III covers a selection of graph polynomials that are of interest in their own right, but can be obtained from the Tutte polynomial. Part IV discusses a range of applications of the Tutte polynomial to mathematics and physics. Part V includes various extensions and generalizations of the Tutte polynomial. Part VI provides a history of the development of the Tutte polynomial.This handbook is not intended to be read linearly. We suggest that readers unfamiliar with the Tutte polynomial begin by reading Chapters 1-4, then dip into the remaining chapters, in any order, according to interest. 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 Graph theory / Joanna A. Ellis-Monaghan, Iain Moffatt -- The Tutte polynomial for graphs / Joanna A. Ellis-Monaghan, Iain Moffatt -- Essential properties of the Tutte polynomial / Béla Bollobás, Oliver Riordan -- Matroid theory / James Oxley -- Tutte polynomial activities / Spencer Backman -- Tutte uniqueness and Tutte equivalence / Joseph E. Bonin, Anna de Mier -- Computational techniques / Criel Merino -- Computational resources / David Pearce, Gordon F. Royle -- The exact complexity of the Tutte polynomial / Tomer Kotek, Johann A. Makowsky -- Approximating the Tutte polynomial / Magnus Bordewich -- Foundations of the chromatic polynomial / Fengming Dong, Khee Meng Koh -- Flows and colorings / Delia Garijo, Andrew Goodall, Jaroslav Nešetřil -- Skein polynomials and the Tutte polynomial when x = y / Joanna A. Ellis-Monaghan, Iain Moffatt -- The interlace polynomial and the Tutte-Martin polynomial / Robert Brijder, Hendrik Jan Hoogeboom -- Network reliability / Jason I. Brown, Charles J. Colbourn -- Codes / Thomas Britz, Peter J. Cameron -- The chip-firing game and the sandpile model / Criel Merino -- The Tutte polynomial and knot theory / Stephen Huggett -- Quantum field theory connections / Adrian Tanasa -- The Potts and random-cluster models / Geoffrey Grimmett -- Where Tutte and Holant meet : a view from counting complexity / Jin-Yi Cai, Tyson Williams -- Polynomials and graph homomorphisms / Delia Garijo, Andrew Goodall, Jaroslav Nešetřil, Guus Regts -- Digraph analogues of the Tutte polynomial / Timothy Y. Chow -- Multivariable, parameterized, and colored extensions of the Tutte polynomial / Lorenzo Traldi -- Zeros of the Tutte polynomial / Bill Jackson -- The U, V and W polynomials / Steven Noble -- Topological extensions of the Tutte polynomial / Sergei Chmutov -- The Tutte polynomial of matroid perspectives / Emeric Gioan -- Hyperplane arrangements and the finite field method / Federico Ardila -- Some algebraic structures related to the Tutte polynomial / Michael J. Falk, Joseph P.S. Kung -- The Tutte polynomial of oriented matroids / Emeric Gioan -- Valuative invariants on matroid basis polytopes / Michael J. Falk, Joseph P.S. Kung -- Non-matroidal generalizations / Gary Gordon, Elizabeth McMahon -- The history of Tutte-Whitney polynomials / Graham Farr The Tutte Polynomial touches on nearly every area of combinatorics as well as many other fields, including statistical mechanics, coding theory, and DNA sequencing. It is one of the most studied graph polynomials.Handbook of the Tutte Polynomial and Related Topics is the first handbook published on the Tutte Polynomial. It consists of thirty-four chapters written by experts in the field, which collectively offer a concise overview of the polynomial's many properties and applications. Each chapter covers a different aspect of the Tutte polynomial and contains the central results and references for its topic. The chapters are organized into six parts. Part I describes the fundamental properties of the Tutte polynomial, providing an overview of the Tutte polynomial and the necessary background for the rest of the handbook. Part II is concerned with questions of computation, complexity, and approximation for the Tutte polynomial; Part III covers a selection of related graph polynomials; Part IV discusses a range of applications of the Tutte polynomial to mathematics, physics, and biology; Part V includes various extensions and generalizations of the Tutte polynomial; and Part VI provides a history of the development of the Tutte polynomial.Features Written in an accessible style for non-experts, yet extensive enough for experts Serves as a comprehensive and accessible introduction to the theory of graph polynomials for researchers in mathematics, physics, and computer science Provides an extensive reference volume for the evaluations, theorems, and properties of the Tutte polynomial and related graph, matroid, and knot invariants Offers broad coverage, touching on the wide range of applications of the Tutte polynomial and its various specializations "The Tutte Polynomial touches on nearly every area of combinatorics as well as many other fields, including statistical mechanics, coding theory, and DNA sequencing. It is one of the most studied graph polynomials. Handbook of the Tutte Polynomial and Related Topics is the first handbook published on the Tutte Polynomial. It consists of thirty-four chapters, written by experts in the field, that collectively offer a concise overview of the polynomial's many properties and applications. Features: Written in an accessible style for non-experts yet extensive enough for experts; Serves as a comprehensive and accessible introduction to the theory of graph polynomials for researchers in mathematics, physics, and computer science; Provides an extensive reference volume for the evaluations, theorems, and properties of the Tutte polynomial and related graph, matroid, and knot invariants; Offers broad coverage, touching on the wide range of applications of the Tutte polynomial and its various specializations"-- Provided by publisher