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

## 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.0005
- Subject:
- Mathematics, Educational Mathematics

This chapter first introduces a notion of 2-connectedness for matroids that extends the corresponding notion for graphs. It then discusses some of the many alternative characterizations of matroid ... 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

## Matroid Theory

*James Oxley*

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

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

Seventy-five years of the study of matroids has seen the development of a rich theory with links to graphs, lattices, codes, transversals,0020and projective geometries. Matroids are of fundamental ... More

## Minors

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

This chapter begins by introducing the operation of contraction as the dual of the operation of deletion. It then derives a definition of contraction that does not use duality and looks at how ... More

## Graphic 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.0006
- Subject:
- Mathematics, Educational Mathematics

This chapter examines graphic matroids in more detail. In particular, it presents several proofs delayed from Chapters 1 and 2, including proofs that a graphic matroid is representable over every ... More

## Representable 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.0007
- Subject:
- Mathematics, Educational Mathematics

This chapter provides an overview of the basic questions associated with matroid representability and indicates how one actually goes about constructing representations. The key ideas are presented ... More

## Constructions

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

This chapter discusses several different ways of using some given set of matroids to form a new matroid. The chapter is organized as follows. Section 7.1 looks at three closely related ways of ... 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

## Submodular Functions and Matroid Union

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

This chapter considers several more matroid constructions. The chapter is organized as follows. Section 11.2 considers several applications of submodular functions, one of which is in the proof of ... More