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

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

*Geoffrey Grimmett and Colin McDiarmid (eds)*

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

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

Professor Dominic Welsh has made significant contributions to the fields of combinatorics and discrete probability, including matroids, complexity, and percolation. He has taught, influenced, and ... More

## EULERIAN AND BIPARTITE ORIENTABLE MATROIDS

*Laura E. Chávez Lomelí and Luis A. Goddyn*

### 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.0002
- Subject:
- Mathematics, Probability / Statistics

This chapter focuses on extending the characterizations of Eulerian graphs via orientations. An Eulerian tour of a graph G induces an orientation with the property that every cocircuit (minimal edge ... 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

## TOWARDS A MATROID-MINOR STRUCTURE THEORY

*Jim Geelen, Bert Gerards, and Geoff Whittle*

### 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.0005
- Subject:
- Mathematics, Probability / Statistics

This chapter surveys recent work aimed at generalizing the results and techniques of the Graph Minors Project of Robertson and Seymour to matroids. Some of the most interesting and apparently ... 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

## NON-SEPARATING CIRCUITS AND COCIRCUITS IN MATROIDS

*Bráulio Maia Junior, Manoel Lemos, and Tereza R. B. Melo*

### 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.0010
- Subject:
- Mathematics, Probability / Statistics

This chapter surveys results about non-separating circuits and cocircuits in graphs and matroids. Some conjectures and open problems are presented.

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

## Duality

*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.0003
- Subject:
- Mathematics, Educational Mathematics

This chapter first defines the dual of a matroid, proves that it is also a matroid, and establishes some fundamental links between matroids and their duals. It then discusses the duals of ... More

## Basic Definitions and Examples

*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.0002
- Subject:
- Mathematics, Educational Mathematics

Matroids can be defined in many different but equivalent ways. This chapter introduces these different axiom systems and proves their equivalence. It also presents various fundamental examples of ... More