Search Results

This chapter provides direct combinatorial proof of an expansion of the Tutte polynomial by independent sets of the matroid. Another expansion of the Tutte polynomial is presented in terms of spanning sets. In the process, it is shown that there is a partition of the set of independent sets of a matroid, such that if the independent set I and the basis B are contained in the same part of the partition, the external activity of I is equal to the external activity of B.

This chapter summarizes the various attempts to extend the Tutte polynomial of a matroid to a polynomial which counts orbits of a group on various sets of objects that the usual Tutte polynomial counts. In other words, the aim is to produce a hybrid of the Tutte polynomial and the cycle index polynomial. There have been various attempts at this, some of which are good for some aims but not for others.

The Tutte-Whitney polynomials play a key role in the study of counting problems on graphs, and have close connections with statistical mechanics and knot theory. This chapter briefly reviews their history and outlines a number of generalizations. It then describes some generalized Tutte-Whitney functions and extends some of these further. These functions are defined for arbitrary collections of sets and for arbitrary binary functions, and have some of the characteristic elements of Tutte-Whitney theory, including interesting partial evaluations and deletion-contraction relations.

This article reviews basic techniques of Fourier analysis on a finite abelian group Q, with subsequent applications in graph theory. These include evaluations of the Tutte polynomial of a graph G in terms of cosets of the Q-flows of G. Other applications to spanning trees of Cayley graphs and to group-valued models on phylogenetic trees are also presented to illustrate methods.

The Tutte polynomial and its relatives play important roles in matroid theory, computational complexity, and models of statistical physics. They provide the natural way to count and relate a variety of objects defined on graphs. This chapter shows that they permit a representation of the two-point correlation function of a ferromagnetic Potts model on a graph G in terms of the flow polynomials of certain related random graphs. This representation extends to general Potts models the so-called random-current expansion for Ising models, and it amplifies the links between the Potts partition function and the Tutte polynomial.

This chapter examines some algorithmic problems associated with matroids. It focuses on determining a ‘fully polynomial randomized approximation scheme’ or ‘FPRAS’. First, the problem of counting matroid bases is considered. Feder and Mihail's polynomial time algorithm for approximating the number of bases in ‘balanced’ matroids is then described, and an improved analysis from Jerrum and Son is presented. The more general problem of evaluating the Tutte polynomial is discussed. This is a two-variable polynomial T(M; x, y) which is associated with a matroid M that encodes much information about M. What is known about the complexity of approximating the Tutte polynomial is reviewed, and the boundary is extended.

This chapter examines the complexity of evaluating graph polynomials, related to the Tutte polynomial, for various classes of matroids. It begins with a short introduction to matroids, complexity, and the Tutte polynomial. The intractability results for the Tutte polynomial are then discussed, including proof of the most often quoted result of classifying the hard points for evaluation of the Tutte polynomial in the graphic case. Contrasting results are presented, giving polynomial time algorithms for restricted classes of input, particularly graphs with bounded tree-width. Finally, the complexity results for various classes of matroids are presented.

Dominic Welsh began writing papers in matroid theory nearly forty years ago. Since then, he has made numerous important contributions to the subject. This chapter reviews Dominic Welsh's work in and influence on the development of matroid theory.

This book concludes with an epilogue, which traces the evolution of graph theory, from the conceptualization of the Königsberg Bridge Problem and its generalization by Leonhard Euler, whose solution led to the subject of Eulerian graphs, to the various efforts to solve the Four Color Problem. It considers elements of graph theory found in games and puzzles of the past, and the famous mathematicians involved including Sir William Rowan Hamilton and William Tutte. It also discusses the remarkable increase since the 1960s in the number of mathematicians worldwide devoted to graph theory, along with research journals, books, and monographs that have graph theory as a subject. Finally, it looks at the growth in applications of graph theory dealing with communication and social networks and the Internet in the digital age and the age of technology.

This chapter addresses the question of whether, for arbitrary n, the property of n-connectedness for graphs can be extended to matroids. It focuses on the case when n = 3. The chapter is organized as follows. Sections 8.1 and 8.2 present Tutte's definition of n-connectedness for matroids and establish some basic properties of the matroid connectivity function and the related local connectivity function. Section 8.3 shows that a matroid is 3-connected if and only if it cannot be decomposed as a direct sum or 2-sum. In addition, it proves a theorem of Cunningham and Edmonds that gives a unique 2-sum decomposition of a connected matroid into 3-connected matroids, circuits, and cocircuits. Section 8.4 discusses some properties of the cycle matroids of wheels and of their relaxations, whirls. Section 8.5 proves Tutte's Linking Theorem, a matroid generalization of Menger's Theorem. Section 8.6 considers the differences between matroid n-connectedness and graph n-connectedness and introduces a matroid generalization of the latter. Section 8.7 proves some extremal connectivity results including Tutte's Triangle Lemma. This lemma is a basic tool in the proof of Tutte's Wheels-and-Whirls Theorem, which is given in Section 8.8.

This chapter discusses the properties of binary matroids. In particular, it proves numerous characterizations of such matroids. It looks at two vector spaces which are commonly associated with a binary matroid. It extends these ideas to a more general class of matroids and touches briefly on Tutte's theory of chain-groups. It shows how 3-sum for graphs can be extended to binary matroids. It concludes with a discussion of several other special properties of binary matroids.

This chapter is organized as follows. Section 10.1 presents Gerards' (1989) proof of Tutte's (1958) excluded-minor characterization of the class of regular matroids. Section 10.2 proves the ternary-matroid result by modifying the proof of Tutte's (1958) excluded-minor characterization of the class of regular matroids. Section 10.3 focuses on graphic matroids and proves Tutte's (1959) excluded-minor characterization of the class of graphic matroids.

This chapter states and proves Seymour's Splitter Theorem. This result, which is a generalization of Tutte's Wheels-and-Whirls Theorem (8.8.4), is a very powerful general tool for deriving matroid structure results. The Wheels-and-Whirls Theorem determines when we can find some element in a 3-connected matroid M to delete or contract in order to preserve 3-connectedness. The Splitter Theorem considers when such an element removal is possible that will not only preserve 3-connectedness but will also maintain the presence of an isomorphic copy of some specified minor of M. The chapter illustrates the power of the Splitter Theorem by noting a variety of consequences of it. It also discusses some extensions and generalizations of the theorem.

This chapter focuses on Hall's Theorem, introduced by British mathematician Philip Hall, and its connection to graph theory. It first considers problems that ask whether some collection of objects can be matched in some way to another collection of objects, with particular emphasis on how different types of schedulings are possible using a graph. It then examines one popular version of Hall's work, a statement known as the Marriage Theorem, the occurrence of matchings in bipartite graphs, Tutte's Theorem, Petersen's Theorem, and the Petersen graph. Peter Christian Julius Petersen introduced the Petersen graph to show that a cubic bridgeless graph need not be 1-factorable. The chapter concludes with an analysis of 1-factorable graphs, the 1-Factorization Conjecture, and 2-factorable graphs.

In this chapter we present some notions of graph theory that will be useful in the rest of the book. It is worth emphasizing that graph theorists and theoretical physicists adopt, unfortunately, different terminologies. We present here both terminologies, such that a sort of dictionary between these two communities can be established. We then extend the notion of graph to that of maps (or of ribbon graphs). Moreover, graph polynomials encoding these structures (the Tutte polynomial for graphs and the Bollobás–Riordan polynomial for ribbon graphs) are presented.

In the first section of this chapter, we use Grassmann calculus, used in fermionic QFT, to give, first a reformulation of the Lingström–Gesse–Viennot lemma proof. We further show that this proof generalizes to graphs with cycles. We then use the same Grassmann calculus techniques to give new proofs of Stembridge's identities relating appropriate graph Pfaffians to sum over non-intersecting paths. The results presented here go further than the ones of Stembridge, because Grassmann algebra techniques naturally extend (without any cost!) to graphs with cycles. We thus obtain, instead of sums over non-intersecting paths, sums over non-intersecting paths and non-intersecting cycles. In the fifth section of the chapter, we give a generalization of these results. In the sixth section of this chapter we use Grassmann calculus to exhibit the relation between a multivariate version of Tutte polynomial and the Kirchhoff-Symanzik polynomials of the parametric representation of Feynman integrals, polynomials already introduced in Chapters 1 and Chapter 3.