Jump to ContentJump to Main Navigation

You are looking at 1-20 of 24 items

  • Keywords: matroids x
Clear All Modify Search

View:

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


View: