UID:
almafu_9959228378702883
Format:
1 online resource (xv, 393 pages) :
,
digital, PDF file(s).
ISBN:
1-107-23956-7
,
1-107-22506-X
,
1-283-52835-5
,
1-139-04944-5
,
9786613840806
,
1-139-52675-8
,
1-139-52794-0
,
1-139-52555-7
,
1-139-53141-7
,
1-139-53022-4
Content:
Matroid theory is a vibrant area of research that provides a unified way to understand graph theory, linear algebra and combinatorics via finite geometry. This book provides the first comprehensive introduction to the field which will appeal to undergraduate students and to any mathematician interested in the geometric approach to matroids. Written in a friendly, fun-to-read style and developed from the authors' own undergraduate courses, the book is ideal for students. Beginning with a basic introduction to matroids, the book quickly familiarizes the reader with the breadth of the subject, and specific examples are used to illustrate the theory and to help students see matroids as more than just generalizations of graphs. Over 300 exercises are included, with many hints and solutions so students can test their understanding of the materials covered. The authors have also included several projects and open-ended research problems for independent study.
Note:
Title from publisher's bibliographic system (viewed on 05 Oct 2015).
,
Cover; Matroids: A Geometric Introduction; Title; Copyright; Dedication; Contents; Preface; Matroids - a quick prehistory; Using this text; Note to instructors; A note to students; Acknowledgements; 1: A tour of matroids; 1.1 Motivation; 1.2 Introduction to matroids; 1.3 Geometries; 1.4 Graphs and matroids; 1.4.1 Graph basics; 1.4.2 Matroids defined from graphs; 1.5 Bipartite graphs and transversal matroids; Exercises; Section 1.2 and 1.3 - Introduction to matroids; Section 1.4 - Graphs and matroids; Section 1.5 - Transversal matroids and other topics; 2: Cryptomorphisms
,
2.1 From independent sets to bases and back again2.2 Circuits and independent sets; 2.3 Rank, flats, hyperplanes and closure; 2.3.1 Rank; 2.3.2 Flat or closed set; 2.3.3 Hyperplanes; 2.3.4 Closure operator; 2.3.5 Cryptomorphism summary; 2.4 Lattice of flats; 2.4.1 Partially ordered sets; 2.4.2 Geometric lattices; 2.5 Tying it together with the rank function; 2.5.1 Rank and independence; 2.5.2 Rank and closure; 2.6 Cryptomorphisms between flats, hyperplanes and closure; 2.6.1 Flats; 2.6.2 Hyperplanes; 2.6.3 Comments about complements; 2.7 Application to optimization: the greedy algorithm
,
ExercisesBasic matroid concepts; Axiom systems - Independent sets and bases; Axiom systems - Rank function; Axiom systems - Closure and flats; Posets and lattices; Greedy algorithm; 3: New matroids from old; 3.1 Matroid deletion and contraction; 3.1.1 Drawing M-e and M/e; 3.1.2 Commutativity of deletion and contraction; 3.2 Deletion and contraction in graphs and representable matroids; 3.2.1 Representable matroids; 3.3 Duality in matroids; 3.3.1 Motivation and examples; 3.3.2 Fundamental results on dual matroids; 3.4 Duality in graphic and representable matroids
,
3.4.1 Duals of graphic matroids3.4.2 Duality in representable matroids; 3.5 Direct sums and connectivity; 3.5.1 Direct sums; 3.5.2 Connected matroids; 3.5.3 Connectivity and rank; 3.5.4 Connectivity motivation from graphs; Exercises; Section 3.1 - Deletion and contraction; Section 3.2 - Deletion and contraction in graphs and matrices; Section 3.3 - Matroid duality; Section 3.4 - Duality in graphic and representable matroids; Section 3.5 - Direct sums; Section 3.5 - Connectivity; 4: Graphic matroids; 4.1 Graphs are matroids; 4.2 Graph versions of matroid theorems
,
4.2.1 Circuit elimination for graphs4.2.2 Circuits, cocircuits and strong basis exchange; 4.3 Duality and cocircuits in graphs; 4.4 Connectivity and 2-isomorphism; Exercises; Section 4.1 - Graphs are matroids; Section 4.2 - Circuits, cocircuits and bases; Section 4.3 - Duality and incidence matrices; Section 4.4 - 2-isomorphism of graphs; 5: Finite geometry; 5.1 Affine geometry and affine dependence; 5.1.1 Affine planes and cartesian coordinates; 5.1.2 Fields and vector spaces; Fields; Vector spaces; 5.1.3 Affine geometry and matroids; 5.2 Affine dependence
,
5.2.1 Rank, closure and hyperplanes for affine geometries
,
English
Additional Edition:
ISBN 0-521-14568-6
Additional Edition:
ISBN 0-521-76724-5
Language:
English
Bookmarklink
