Atnaujinkite slapukų nuostatas

El. knyga: Handbook of the Tutte Polynomial and Related Topics

Edited by (Saint Michael's College, Colchester, Vermont, USA), Edited by
  • Formatas: 804 pages
  • Išleidimo metai: 06-Jul-2022
  • Leidėjas: Chapman & Hall/CRC
  • Kalba: eng
  • ISBN-13: 9780429529177
Kitos knygos pagal šią temą:
Handbook of the Tutte Polynomial and Related TopicsDidesnis paveikslėlis
  • Formatas: 804 pages
  • Išleidimo metai: 06-Jul-2022
  • Leidėjas: Chapman & Hall/CRC
  • Kalba: eng
  • ISBN-13: 9780429529177
Kitos knygos pagal šią temą:

DRM apribojimai

  • Kopijuoti:

    neleidžiama

  • Spausdinti:

    neleidžiama

  • El. knygos naudojimas:

    Skaitmeninių teisių valdymas (DRM)
    Leidykla pateikė šią knygą šifruota forma, o tai reiškia, kad norint ją atrakinti ir perskaityti reikia įdiegti nemokamą programinę įrangą. Norint skaityti šią el. knygą, turite susikurti Adobe ID . Daugiau informacijos  čia. El. knygą galima atsisiųsti į 6 įrenginius (vienas vartotojas su tuo pačiu Adobe ID).

    Reikalinga programinė įranga
    Norint skaityti šią el. knygą mobiliajame įrenginyje (telefone ar planšetiniame kompiuteryje), turite įdiegti šią nemokamą programėlę: PocketBook Reader (iOS / Android)

    Norint skaityti šią el. knygą asmeniniame arba „Mac“ kompiuteryje, Jums reikalinga  Adobe Digital Editions “ (tai nemokama programa, specialiai sukurta el. knygoms. Tai nėra tas pats, kas „Adobe Reader“, kurią tikriausiai jau turite savo kompiuteryje.)

    Negalite skaityti šios el. knygos naudodami „Amazon Kindle“.

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 polynomials 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

Recenzijos

"This is a comprehensive reference text on the Tutte polynomial, including its applications and extensions. The book consists of 34 relatively short chapters written by different contributing authors. The individual contributors present the most important theorems in their respective fields and illustrate them with examples. Each chapter ends with a list of open problems. Two brief introductory chapters by the editorsEllis-Monaghan (Univ. of Amsterdam) and Moffatt (Royal Holloway, University of London)cover the basic definitions and computational results for Tutte polynomials. The next two-thirds of the book are devoted to applications and extensions, that is, uses and occurrences of Tutte polynomials outside graph theory or matroid theory. Hyperplane arrangements, quantum field theory, network reliability, the sandpile model, and chipfiring games are a few examples of the topics treated. The book concludes with a chapter on the history of the subject written by Graham Farr. It follows from the nature of the volume (i.e., no proofs, no exercises, very broad topical coverage, and more than 50 authors) that classroom use of the book is unlikely. Nonetheless, this work is likely to become the most frequently consulted reference on Tutte polynomials."

Summing Up: Highly recommended. Graduate students and faculty.

-Choice Review

Preface xv
Contributors xvii
I Fundamentals
1(138)
1 Graph theory
3(11)
Joanna A. Ellis-Monaghan
Iain Moffatt
1.1 Introduction
3(1)
1.2 Graph theory conventions
3(11)
2 The Tutte polynomial for graphs
14(13)
A. Joanna
Ellis-Monaghan
Iain Moffatt
2.1 Introduction
14(1)
2.2 The standard definitions of the Tutte polynomial
15(8)
2.3 Multiplicativity
23(1)
2.4 Universality of the Tutte polynomial
24(2)
2.5 Duality
26(1)
3 Essential properties of the Tutte polynomial
27(17)
Bela Bollobds
Oliver Riordan
3.1 Introduction
28(1)
3.2 Evaluations at special points
28(4)
3.3 Coefficient properties and irreducibility
32(2)
3.4 Evaluations along curves
34(2)
3.5 Dual graphs and medial graphs
36(3)
3.6 Knots
39(3)
3.7 Signed, colored and topological Tutte polynomials
42(1)
3.8 Open problems
43(1)
4 Matroid theory
44(42)
James Oxley
4.1 Introduction
44(1)
4.2 Fundamental examples and definitions
45(6)
4.3 The many faces of a matroid
51(3)
4.4 Duality
54(6)
4.5 Basic constructions
60(10)
4.6 More examples
70(3)
4.7 The Tutte polynomial of a matroid
73(8)
4.8 Some particular evaluations
81(4)
4.9 Some basic identities
85(1)
5 Tutte polynomial activities
86(14)
Spencer Backman
5.1 Introduction
86(1)
5.2 Activities for maximal spanning forests
87(1)
5.3 Activity bipartition
88(1)
5.4 Activities for subgraphs
89(1)
5.5 Depth-first search external activity
90(1)
5.6 Activities via combinatorial maps
91(2)
5.7 Unified activities for subgraphs via decision trees
93(1)
5.8 Orientation activities
94(2)
5.9 Active orders
96(1)
5.10 Shellability and activity
97(2)
5.11 Open problems
99(1)
6 Tutte uniqueness and Tutte equivalence
100(39)
Joseph E. Bonin
Anna de Mier
6.1 Introduction
100(1)
6.2 Basic notions and results, and initial examples
101(7)
6.3 Tutte uniqueness and equivalence for graphs
108(8)
6.4 Tutte uniqueness and equivalence for matroids
116(17)
6.5 Related results
133(4)
6.6 Open problems
137(2)
II Computation
139(72)
7 Computational techniques
141(20)
Criel Merino
7.1 Introduction
141(1)
7.2 Direct computation
142(3)
7.3 Duality and matroid operations
145(2)
7.4 Using equivalent polynomials
147(4)
7.5 Transfer matrix method
151(2)
7.6 Decomposition
153(3)
7.7 Counting arguments
156(2)
7.8 Other strategies
158(1)
7.9 Computation for common graphs and matroids
159(1)
7.10 Open problems
159(2)
8 Computational resources
161(14)
David Pearce
Gordon F. Royle
8.1 Introduction
161(1)
8.2 Implementations
162(8)
8.3 Comparative performance
170(2)
8.4 Conclusions
172(1)
8.5 Open problems
173(2)
9 The exact complexity of the Tutte polynomial
175(19)
Tomer Kotek
Johann A. Makowsky
9.1 Introduction
175(1)
9.2 Complexity classes and graph width
176(3)
9.3 Exact evaluations on graphs
179(5)
9.4 Exact evaluation on matroids
184(6)
9.5 Algebraic models of computation
190(2)
9.6 Open problems
192(2)
10 Approximating the Tutte polynomial
194(17)
Magnus Bordewich
10.1 Introduction
194(2)
10.2 Notation
196(1)
10.3 Randomized approximation schemes
196(3)
10.4 Positive approximation results
199(4)
10.5 Negative results: inapproximability
203(5)
10.6 The quantum connection
208(1)
10.7 Open problems
209(2)
III Specializations
211(94)
11 Foundations of the chromatic polynomial
213(39)
Fengming Dong
Khee Meng Koh
11.1 Introduction
213(1)
11.2 Computing chromatic polynomials
214(6)
11.3 Properties of chromatic polynomials
220(12)
11.4 Chromatically equivalent graphs
232(9)
11.5 Roots of chromatic polynomials
241(6)
11.6 Open problems
247(5)
12 Flows and colorings
252(14)
Delia Garijo
Andrew Goodall
Jaroslav Nesetfil
12.1 Introduction
252(1)
12.2 Flows and the flow polynomial
253(4)
12.3 Coloring-flow convolution formulas
257(4)
12.4 A-bicycles
261(2)
12.5 Open problems
263(3)
13 Skein polynomials and the Tutte polynomial when x = y
266(18)
Joanna A. Ellis-Monaghan
Iain Moffatt
13.1 Introduction
266(1)
13.2 Vertex states, graph states, and skein relations
267(2)
13.3 Skein polynomials
269(11)
13.4 Evaluations of the Tutte polynomial along x = y
280(3)
13.5 Open problems
283(1)
14 The interlace polynomial and the Tutte-Martin polynomial
284(21)
Robert Brijder
Hendrik Jan Hoogeboom
14.1 Introduction
284(1)
14.2 Notation
285(1)
14.3 Interlace polynomial
286(5)
14.4 Martin polynomial
291(1)
14.5 Global interlace polynomial
292(2)
14.6 Two-variable interlace polynomial
294(1)
14.7 Weighted interlace polynomial
295(1)
14.8 Connection with the Tutte polynomial
296(1)
14.9 Isotropic systems and the Tutte--Martin polynomial
297(1)
14.10 Interlace polynomials for delta-matroids
298(4)
14.11 Summary
302(1)
14.12 Open problems
303(2)
IV Applications
305(118)
15 Network reliability
307(21)
Jason I. Brown
Charles J. Colbourn
15.1 Introduction
308(2)
15.2 Forms of the reliability polynomial
310(4)
15.3 Calculating coefficients
314(1)
15.4 Transformations
315(1)
15.5 Coefficient inequalities
316(5)
15.6 Analytic properties of reliability
321(3)
15.7 Open problems
324(4)
16 Codes
328(17)
Thomas Britz
Peter J. Cameron
16.1 Introduction
328(1)
16.2 Linear codes and the Tutte polynomial
329(5)
16.3 Ordered tuples and subcodes
334(3)
16.4 Equivalence of the Tutte polynomial and weights
337(1)
16.5 Orbital polynomials
337(2)
16.6 Other generalizations and applications
339(1)
16.7 Wei's duality theorem
340(3)
16.8 Open problems
343(2)
17 The chip-firing game and the sandpile model
345(7)
Criel Merino
17.1 Introduction
345(1)
17.2 The Tutte polynomial and the chip-firing game
346(2)
17.3 Sandpile models
348(1)
17.4 The critical group and parking functions
349(2)
17.5 Open problems
351(1)
18 The Tutte polynomial and knot theory
352(16)
Stephen Huggett
18.1 Introduction
352(1)
18.2 Graphs and links
353(2)
18.3 Polynomial invariants of links
355(2)
18.4 The Tutte and Jones polynomials
357(2)
18.5 The Tutte and HOMFLYPT polynomials
359(1)
18.6 Applications in knot theory
360(2)
18.7 The Bollobas--Riordan polynomial
362(2)
18.8 Categorification
364(2)
18.9 Open problems
366(2)
19 Quantum field theory connections
368(10)
Adrian Tanasa
19.1 Introduction
368(1)
19.2 The Symanzik polynomials as evaluations of the multivariate Tutte polynomial
369(1)
19.3 The Symanzik polynomials in quantum field theory
370(5)
19.4 Hopf algebras and the Tutte polynomial
375(2)
19.5 Open problems
377(1)
20 The Potts and random-cluster models
378(17)
Geoffrey Grimmett
20.1 Introduction
378(1)
20.2 Probabilistic models from physics
379(6)
20.3 Phase transition
385(1)
20.4 Basic properties of random-cluster measures
386(1)
20.5 The Limit as q ↓ 0
387(3)
20.6 Flow polynomial
390(1)
20.7 The limit of zero temperature
391(1)
20.8 The random-cluster model on the complete graph
392(1)
20.9 Open problems
393(2)
21 Where Tutte and Holant meet: a view from counting complexity
395(10)
Jin-Yi Cai
Tyson Williams
21.1 Introduction
395(1)
21.2 Definition of Holant and related concepts
396(2)
21.3 Specializations of the Tutte polynomial with local expressions
398(5)
21.4 Open problems
403(2)
22 Polynomials and graph homomorphisms
405(18)
Delia Garijo
Andrew Goodall
Jaroslav Nesetfil
Guus Regts
22.1 Introduction
405(2)
22.2 Homomorphism profiles
407(3)
22.3 Edge coloring models
410(2)
22.4 Connection matrices
412(2)
22.5 Matroid invariants
414(1)
22.6 Graph polynomials from homomorphism profiles
415(2)
22.7 Graph polynomials by recurrence formulas
417(4)
22.8 Open problems
421(2)
V Extensions
423(198)
23 Digraph analogues of the Tutte polynomial
425(15)
Timothy Y. Chow
23.1 Introduction
425(1)
23.2 The cover polynomial
426(7)
23.3 Tutte invariants for alternating dimaps
433(3)
23.4 Gordon--Traldi polynomials
436(3)
23.5 The B-polynomial
439(1)
23.6 Open problems
439(1)
24 Multivariable, parameterized, and colored extensions of the Tutte polynomial
440(21)
Lorenzo Traldi
24.1 Introduction
440(1)
24.2 Parameterized and multivariate Tutte polynomials
441(4)
24.3 Identities for parameterized Tutte polynomials
445(4)
24.4 Related parameterized polynomials
449(4)
24.5 Four parameters: colored and strong extensions
453(5)
24.6 Ported polynomials and others
458(1)
24.7 Open problems
459(2)
25 Zeros of the Tutte polynomial
461(12)
Bill Jackson
25.1 Introduction
461(1)
25.2 The multivariate Tutte polynomial
462(2)
25.3 Zero-free regions in R2
464(4)
25.4 Density of real zeros
468(2)
25.5 Determining the sign of the Tutte polynomial
470(1)
25.6 Complex zeros
470(2)
25.7 Open problems
472(1)
26 The U, V, and W polynomials
473(24)
Steven Noble
26.1 Introduction
473(4)
26.2 Properties of the polynomials
477(9)
26.3 Equivalent polynomials and symmetric functions
486(5)
26.4 Graphs determined by their U-polynomial
491(1)
26.5 Complexity issues
492(2)
26.6 Related polynomials
494(1)
26.7 Open problems
495(2)
27 Topological extensions of the Tutte polynomial
497(17)
Sergei Chmutov
27.1 Introduction
497(2)
27.2 Ribbon graphs
499(2)
27.3 The Bollobas--Riordan polynomial
501(1)
27.4 The Las Vergnas polynomial
502(1)
27.5 The Krushkal polynomial
503(3)
27.6 Polynomials from deletion--contraction relations
506(2)
27.7 Polynomials arising from flows and tensions
508(1)
27.8 Quasi-trees
509(3)
27.9 Open problems
512(2)
28 The Tutte polynomial of matroid perspectives
514(18)
Emeric Gioan
28.1 Introduction
514(1)
28.2 Matroid perspectives
515(1)
28.3 The Tutte polynomial of a matroid perspective
516(3)
28.4 Deletion-contraction, convolution, and the Mobius function
519(1)
28.5 Subset activities in matroids and perspectives
520(2)
28.6 Five-variable expansion and partial derivatives
522(2)
28.7 Representable and binary cases
524(2)
28.8 Brief accounts of related polynomials
526(4)
28.9 Open problems
530(2)
29 Hyperplane arrangements and the finite field method
532(19)
Federico Ardila
29.1 Introduction
532(1)
29.2 Hyperplane arrangements
533(3)
29.3 Polynomial invariants
536(2)
29.4 Topological and algebraic invariants
538(3)
29.5 The finite field method
541(2)
29.6 A catalog of characteristic and Tutte polynomials
543(4)
29.7 Multivariate and arithmetic Tutte polynomials
547(3)
29.8 Open problems
550(1)
30 Some algebraic structures related to the Tutte polynomial
551(14)
Michael J. Falk
Joseph P.S. Rung
30.1 Introduction
551(1)
30.2 Orlik--Solomon algebras
552(10)
30.3 Coalgebras associated with matroids
562(1)
30.4 Open problems
563(2)
31 The Tutte polynomial of oriented matroids
565(25)
Emeric Gioan
31.1 Introduction
565(1)
31.2 Oriented matroids and related structures
566(6)
31.3 Tutte polynomial in terms of orientation-activities
572(2)
31.4 Counting bounded regions and bipolar orientations
574(1)
31.5 Generalizations to oriented matroid perspectives
575(2)
31.6 Activity classes and active partitions
577(2)
31.7 Filtrations in matroids and β-invariants of minors
579(2)
31.8 The active basis and the canonical active bijection
581(4)
31.9 Reorientations/subsets bijection, refined orientation-activities
585(1)
31.10 Counting circuit/cocircuit reversal classes
586(3)
31.11 Open problems
589(1)
32 Valuative invariants on matroid basis polytopes
590(8)
Michael J. Falk
Joseph P.S. Kung
32.1 Introduction
590(1)
32.2 Valuative functions on matroid base polytopes
591(6)
32.3 Open problems
597(1)
33 Non-matroidal generalizations
598(23)
Gary Gordon
Elizabeth McMahon
33.1 Introduction
598(3)
33.2 Greedoids and the Tutte polynomial
601(6)
33.3 Antimatroids
607(8)
33.4 The β-invariant
615(3)
33.5 Open problems
618(3)
VI History
621(48)
34 The history of Tutte-Whitney polynomials
623(46)
Graham Farr
34.1 Introduction
623(2)
34.2 The classic papers
625(2)
34.3 Preliminaries
627(3)
34.4 Notation in the papers
630(1)
34.5 Whitney, 1932: A logical expansion in mathematics
631(1)
34.6 Whitney, 1932: The coloring of graphs
632(6)
34.7 Whitney, 1933: Topological invariants for graphs
638(1)
34.8 Tutte, 1947: A ring in graph theory
639(8)
34.9 Tutte's PhD thesis
647(2)
34.10 Tutte, 1954: A contribution to the theory of chromatic polynomials
649(2)
34.11 Tutte, 1967: On dichromatic polynomials
651(5)
34.12 Potts, 1952: Some generalized order-disorder transformations
656(2)
34.13 Zykov
658(1)
34.14 Some other work
659(2)
34.15 Closing remarks
661(8)
Acknowledgments 669(1)
Bibliography 670(80)
Selected evaluations and interpretations 750(9)
Symbols 759(8)
Index 767
Joanna A. Ellis-Monaghan is a professor of discrete mathematics at the Korteweg - de Vries Instituut voor Wiskunde at the Universiteit van Amsterdam. Her research focuses on algebraic combinatorics, especially graph polynomials, as well as applications of combinatorics to DNA self-assembly, statistical mechanics, computer chip design, and bioinformatics. She also has an interest in mathematical pedagogy. She has published over 50 papers in these areas.

Iain Moffatt is a professor of mathematics in Royal Holloway, University of London. His main research interests lie in the interactions between topology and combinatorics. He is especially interested in graph polynomials, topological graph theory, matroid theory, and knot theory. He has written more than 40 papers in these areas and is also the author of the book An Introduction to Quantum and Vassiliev Knot invariants.

Ellis-Monaghan and Moffatt have authored several papers on the Tutte polynomial and related graph polynomials together as well as the book Graphs on surfaces: Dualities, Polynomials, and Knots.
Daugiau apie elektronines knygas Daugiau apie elektronines knygas
Pastovi nuoroda: https://www.kriso.lt/db/97804295291776e.html
Raktažodžiai: