View:

- no detail
- some detail
- full detail

## EXPANDING THE TUTTE POLYNOMIAL OF A MATROID OVER THE INDEPENDENT SETS

*Koko Kalambay Kayibi*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0011
- Subject:
- Mathematics, Probability / Statistics

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 ... More

## ORBIT COUNTING AND THE TUTTE POLYNOMIAL

*Peter J. Cameron*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0001
- Subject:
- Mathematics, Probability / Statistics

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 ... More

## TUTTE-WHITNEY POLYNOMIALS: SOME HISTORY AND GENERALIZATIONS

*Graham E. Farr*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0003
- Subject:
- Mathematics, Probability / Statistics

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 ... More

## FOURIER ANALYSIS ON FINITE ABELIAN GROUPS: SOME GRAPHICAL APPLICATIONS

*Andrew Goodall*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0007
- Subject:
- Mathematics, Probability / Statistics

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 ... More

## FLOWS AND FERROMAGNETS

*Geoffrey Grimmett*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0008
- Subject:
- Mathematics, Probability / Statistics

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 ... More

## APPROXIMATING THE TUTTE POLYNOMIAL

*Mark Jerrum*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0009
- Subject:
- Mathematics, Probability / Statistics

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 ... More

## COMPLEXITY OF GRAPH POLYNOMIALS

*Steven D. Noble*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0013
- Subject:
- Mathematics, Probability / Statistics

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, ... More

## THE CONTRIBUTIONS OF DOMINIC WELSH TO MATROID THEORY

*James Oxley*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0015
- Subject:
- Mathematics, Probability / Statistics

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 ... More

## Graph Theory: A Look Back—The Road Ahead

*Arthur Benjamin, Gary Chartrand, and Ping Zhang*

### in The Fascinating World of Graph Theory

- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175638
- eISBN:
- 9781400852000
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175638.003.0013
- Subject:
- Mathematics, Applied Mathematics

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 ... More

## Higher Connectivity

*James Oxley*

### in Matroid Theory

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780198566946
- eISBN:
- 9780191774904
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566946.003.0009
- Subject:
- Mathematics, Educational Mathematics

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 ... More

## Binary Matroids

*James Oxley*

### in Matroid Theory

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780198566946
- eISBN:
- 9780191774904
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566946.003.0010
- Subject:
- Mathematics, Educational Mathematics

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 ... More

## Excluded-Minor Theorems

*James Oxley*

### in Matroid Theory

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780198566946
- eISBN:
- 9780191774904
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566946.003.0011
- Subject:
- Mathematics, Educational Mathematics

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 ... More

## The Splitter Theorem

*James Oxley*

### in Matroid Theory

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780198566946
- eISBN:
- 9780191774904
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566946.003.0013
- Subject:
- Mathematics, Educational Mathematics

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 ... More

## Factoring Graphs

*Arthur Benjamin, Gary Chartrand, and Ping Zhang*

### in The Fascinating World of Graph Theory

- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175638
- eISBN:
- 9781400852000
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175638.003.0007
- Subject:
- Mathematics, Applied Mathematics

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 ... More

## Graphs, ribbon graphs, and polynomials

*Adrian Tanasa*

### in Combinatorial Physics: Combinatorics, Quantum Field Theory, and Quantum Gravity Models

- Published in print:
- 2021
- Published Online:
- May 2021
- ISBN:
- 9780192895493
- eISBN:
- 9780191914973
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780192895493.003.0002
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

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, ... More

## Fermionic QFT, Grassmann calculus, and combinatorics

*Adrian Tanasa*

### in Combinatorial Physics: Combinatorics, Quantum Field Theory, and Quantum Gravity Models

- Published in print:
- 2021
- Published Online:
- May 2021
- ISBN:
- 9780192895493
- eISBN:
- 9780191914973
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780192895493.003.0006
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

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 ... More

View:

- no detail
- some detail
- full detail