MAA Short Course on What is a Matroid? Theory and Applications from the Ground Up
MAA Sectional Meetings  |  AMS Sectional Meetings  |  MAA National Meetings  |  AMS National Meetings |  Inquiries: meet@ams.org  | Search Here


2011 JMM, Jan 6 - 9, 2011, New Orleans Marriott, Sheraton New Orleans, Largest Annual Mathematics Meeting in the World

HOME
   Highlighted Speakers
PROGRAM
   Prog List by Orgs
   Full Program
   Timetable
   Student Programs
COURSES/ANCILLARY WORKSHOPS
   AMS Short Courses
››MAA Short Course
   MAA Minicourses
   MAA Ancillary Workshops
COMMITTEES
DAYCARE
EXHIBITS
   Exhibits and Sponsors
   Call for Mathematical Art
EMPLOYMENT CENTER
GENERAL
   Deadlines
   Local Info/Events
   Miscellaneous
   Frequently Asked Questions
HOUSING
   Roommate Search Board
   How to Get a Room
   Hotel Information
   Map
   Registration/Housing Form
REGISTRATION
   How To Register
   Fees and Categories
   Registration/Housing Form
SOCIAL
   List of Events by Orgs
   Newcomers Guide
   Networking Opportunities
   Student Activities
TRAVEL
CONTACT US


Networking Opportunities

Wiki here
facebook Join Us on Facebook

Follow JointMath on Twitter

|

official airline of the meeting

MAA Short Course

(For updated locations, click here; All locations are subject to change)
Click here for pdf of this announcement

This two-day Short Course on What is a Matroid? Theory and Applications, from the Ground Up is organized by Nancy Ann Neudauer, Pacific University, and will take place on Tuesday and Wednesday, January 4 and 5, before the annual meeting begins.

Advance registration fees are: member of the AMS or MAA, US$150; nonmembers are US$200; students, unemployed, or emeritus are US$75. These fees are in effect until December 15. If you choose to register at the meeting, the fees are US$160 for members of the AMS or MAA, US$210 for nonmembers, and US$85 for students, unemployed, or emeritus.

What is a matroid? Theory and Applications, from the ground up

Location: Rhythms III, 2nd Floor, Sheraton
Organiser: Nancy Ann Neudauer, Pacific University

Gian-Carlo Rota said that "Anyone who has worked with matroids has come away with the conviction that matroids are one of the richest and most useful ideas of our day." [20]

Hassler Whitney introduced the theory of matroids in 1935 and developed a striking number of their basic properties as well as different ways to formulate the notion of a matroid. As more and more connections between matroid theory and other fields have been discovered in the ensuing decades, it has been realized that the concept of a matroid is one of the most fundamental and powerful in mathematics. Examples of matroids arise from networks, matrices, configurations of points, arrangements of hyperplanes, and geometric lattices; matroids play an essential role in combinatorial optimization. We all know some matroids, but not always by name.

In mathematics, notions of independence akin to linear independence arise in various contexts; matroids surface naturally in these situations. We provide a brief, accessible introduction so that those interested in matroids have a place to start. We look at connections between seemingly unrelated mathematical objects, and show how matroids have unified and simplified diverse areas.

An introduction to matroids can be found in An Introduction to Matroid Theory [28], in the AMS Feature Column, Matroids: The Value of Abstraction [17], and in Matroids You Have Known [18]. The two books entitled Matroid Theory [19] and [22] provide a strong foundation, as does the series Theory of Matroids [26], Matroid Applications [25], and Combinatorial Geometries [24]. Many of the key early papers are reprinted in A source book in matroid theory [14] with illuminating commentaries.

Early work on matroids [8] can be found by H. Whitney [27], G. Birkhoff [2], S. Maclane [16], and B.L. van der Waerden [21]. For background in graph theory, see the graph theory books of West [23], Diestel [9], Wilson [29], or Harary [12]. For background in combinatorics, see Introductory Combinatorics [4] or [7]. For applications of matroids, see Combinatorial Optimization: Networks and Matroids [15], the three chapters on matroid theory in Handbook of Combinatorics [10], and Matroid Applications [25]. For some connections of matroids to other areas of discrete mathematics, see Discrete and Combinatorial Mathematics: An Applied Introduction [11] and The Many Names of (7,3,1) [5].

Format

This Short Course will take place over two days and consist of eight talks, each of 60-75 minutes. The talks on the first day will provide an introduction to matroid theory and some of the foundations of matroids. Day two talks will discuss more specialized topics and contain an overview of research in matroids and some of the big current research questions. All speakers will be encouraged to discuss research questions including projects conducted with students.

Joseph Bonin, Gary Gordon, Winfried Hochstättler, Dillon Mayhew, Jennifer McNulty, Nancy Ann Neudauer, and James Oxley are speakers in this Short Course. Gary Gordon and Jennifer McNulty are currently writing an undergraduate text on matroids; James Oxley has written a widely-used graduate text on matroids.

Top of page

Talk 1: Matroids You Have Known

Speaker: Nancy Ann Neudauer, Pacific University

We provide here an initial exposure to matroids and introduction to the short course. We illustrate that matroids arise naturally several times in the undergraduate curriculum, and begin with two structures familiar to most undergraduates, vector spaces and graphs. Common traits of these two structures are emphasized, and used to motivate the definition of a matroid in general. We extend this to discuss basic properties of the matroid. Other matroids the audience has probably not seen are then introduced.

Talk 2: Cryptomorphisms and Optimization

Speaker: Jenny McNulty, University of Montana

One of the useful aspects (and peculiarities) of matroids, is that they can be defined in many equivalent yet seemingly different ways. These definitions are motivated from linear algebra (e.g. bases, independent sets), graph theory (e.g. circuits, cocircuits) and geometry (e.g. closure, hyperplanes). Each formulation of the definition contains a finite ground set E and a family of subsets of E or a function defined on 2E; these subsets and functions will satisfy various axioms. A cryptomorphism is a method for converting from one system to another. Kruskal’s algorithm for finding a minimum weight spanning tree of a connected graph can be generalized to that of finding a minumum weight basis of a matroid. Somewhat surprisingly, this greedy algorithm also gives another method for defining a matroid, namely as the structure for which the algorithm is correct.

Background reading is found in the Appendix of Matroid Cryptomorphisms and the chapter on Axiom Systems in Theory of Matroids [26], the first chapter of Matroid Theory [19], and in On the abstract properties of linear dependence [27].

Talk 3: Matroid Representations

Speaker: Gary Gordon, Lafayette College

Matroid representations generalize some beautiful and old theorems from projective geometry, including results of Pappus of Alexandria (c. 200 AD) and Descartes. We'll see how these famous configurations can be interpreted as matroids and study their representability. We'll conclude with more current research questions on matroid representability.

Talk 4: Matroid Operations

Speaker: Dillon Mayhew, Victoria University of Wellington

We interpret the title of this talk quite informally, and we take a matroid operation to be any procedure which produces a new matroid from matroids already given to us.

The most basic matroid operations involve removing elements from a matroid. This can be done in two ways: by deletion or contraction. These operations are analogs of graph operations: we can delete or contract an edge from a graph. This naturally leads to the notion of a matroid minor, that is, a matroid produced by a sequence of deletions and contractions. Most natural classes of matroids are closed under the operations of deletion and contraction, and can therefore be characterized by their excluded minors. These are matroids that are not in the class, with the property that any deletion or contraction produces a matroid in the class. Some of the most celebrated theorems in matroid theory characterize classes of matroids by giving their excluded minors.

Another basic operation involves duality. Matroid duals are analogues of orthogonal codes in coding theory. Duality is intimately connected to deletion and contraction; in fact, it interchanges these two operations.

Other operations we will discuss involve joining two matroids in some way so as to produce another matroid. Operations that fit this description include matroid sums and matroid unions.

Treatments of matroid operations can be found in Brylawski's chapter in Theory of Matroids [26] or in Matroid Theory [19].

Top of page

Talk 5: Transversal Matroids

Speaker: Joseph Bonin, The George Washington University

Given a finite sequence A = (A1,A2, . . . , Ar) of subsets of a finite set S, a partial transversal of A is a subset X of S for which there is an injection f : X {1, 2, . . . , r} with x A f (x) for all x X. A fundamental result of J. Edmonds and D. R. Fulkerson is that the partial transversals of any such sequence A are the independent sets of a matroid on S. These matroids, which are called transversal matroids, form a much-studied and important class of matroids. In this talk we present several ways to view transversal matroids, we treat some of their basic properties, and we prove several useful characterizations of these matroids. We also discuss a relatively newly introduced class of transversal matroids that arise from lattice paths; we use these lattice path matroids to provide appealing illustrations of topics from other parts of the course and to expand the range of topics covered. (See pdf version for correct mathematical formulas, etc..)

References for transversal matroids include Transversal matroids [6], Transversal matroids and related structures [13], Matroid Theory [19], and Matroid Theory [22].

Talk 6: Oriented Matroids

Speaker: Winfried Hochstättler, FernUniversität in Hagen, Germany

While matroids can be considered a combinatorial model of linear and affine dependency, oriented matroids comprise the combinatorics of convex linear geometry. Vector spaces over ordered fields and digraphs yield first examples and most of the cryptomorphic axiom systems for matroids have "oriented counterparts".

Matroids that are orientable admit a representation as pseudosphere systems which may be considered as hyperplane arrangements where the hyperplanes are allowed to have small local deviations from linearity. Oriented matroids of rank three correspond to pseudoline arrangements in the plane, in arbitrary rank they provide a tool to study the combinatorics of polyhedra and linear programming, e.g. the well known finite pivoting rule of Robert Bland was developed in the context of oriented matroid programming.

The standard reference is Oriented Matroids [3]. An easily accessible introduction is given in Linear Programming Duality: An Introduction to Oriented Matroids [1]. Chapter 6 of the Handbook of Combinatorics [10] grants fast access.

Talk 7: Research in matroids

Speaker: James Oxley, Louisiana State University

The two fundamental examples of matroids considered in Whitney's seminal paper were derived from graphs and from matrices. These two basic classes of matroids continue to motivate much of the current research in matroid theory. This talk will review some of the exciting recent work in matroid theory that is inspired by the Graph-Minors Project of Robertson and Seymour and by a forty-year old conjecture of Rota on which matroids arise from matrices over finite fields.

Concluding Session: Tying it together

All speakers

A review session and panel discussion.

Top of page

References

[1] A. Bachem, W. Kern, Linear Programming Duality: An Introduction to Oriented Matroids, Springer, Berlin etc., (1992).

[2] Birkhoff, Garrett, Abstract Linear Dependence and Lattices, Amer. J. Math. 57 (1935) 800-804.

[3] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. M. Ziegler, Oriented Matroids (Encyclopedia of Mathematics and its Applications 46), Cambridge University Press, (1993).

[4] Kenneth P. Bogart, Introductory Combinatorics, Third Edition, Harcourt Academic Press, San Diego, CA, 2000.

[5] Ezra Brown, The Many Names of (7,3,1), Mathematics Magazine, 75 (Apr., 2002), 83-94.

[6] R. A. Brualdi, Transversal matroids, in: Combinatorial Geometries, N. White, ed. (Cambridge Univ. Press, Cambridge, 1987) 72–97.

[7] Richard A. Brualdi, Introductory Combinatorics, Fifth Edition, Prentice Hall, New York, NY, 2009.

[8] Tom Brylawski, A partially-anecdotal history of matroids, talk given at “Matroids in Montana” workshop, November, 2006.

[9] Reinhard Diestel, Graph Theory, Third Edition, Springer-Verlag, Berlin, 173, 2005.

[10] R.L. Graham, M. Gr¨otschel, L. Lovász, ed., Handbook of Combinatorics, MIT Press, Cambridge, MA, 1995.

[11] Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Pearson/Addison-Wesley, Boston, MA, 2004.

[12] Frank Harary, Graph Theory, Addison-Wesley Publishing Company, Reading, MA, 1972.

[13] A. W. Ingleton, Transversal matroids and related structures, in: Higher Combinatorics, M. Aigner, ed. (Proc. NATO Advanced Study Inst., Berlin, 1976; Reidel, Dordrecht-Boston, MA, 1977) 117–131.

[14] Joseph P.S. Kung, A source book in matroid theory, Birkh¨auser Boston Inc, Boston, MA, 1986.

[15] Eugene Lawler, Combinatorial Optimization: Networks and Matroids, Dover Publications, Inc., Mineola, NY, 2001.

[16] Saunders MacLane, Some interpretations of abstract linear dependence in terms of projective geometry, Amer. J. Math., 58 (1936), 236-240.

[17] Joseph Malkevitch, Matroids: The Value of Abstraction, AMS Feature Column, http://www.ams.org/featurecolumn/archive/matroids1.html (January, 2003).

[18] David L. Neel and Nancy Ann Neudauer, Matroids You Have Known, Mathematics Magazine, 82 (2009).

[19] James G. Oxley, Matroid Theory, Oxford University Press, Oxford, UK, 1992.

[20] Gian-Carlo Rota, Indiscrete Thoughts, Birkhäuser, Boston, MA, 1996.

[21] B.L. van der Waerden, Moderne Algebra, Second Edition, Springer, Berlin, Germany, 1937.

[22] D.J.A. Welsh, Matroid Theory, Academic Press, London-New York, 1976.

[23] Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2000.

[24] N. White, ed., Combinatorial Geometries, Cambridge, New York, NY, 29, 1987.

[25] N. White, ed., Matroid Applications, Cambridge, New York, NY, 40, 1992.

[26] N. White, ed., Theory of Matroids, Cambridge, New York, NY, 26, 1986.

[27] Hassler Whitney, On the abstract properties of linear dependence, Amer. J. Math., 57 (1935), 509-533.

[28] Robin J. Wilson, An Introduction to Matroid Theory, Amer. Math. Monthly, 80 (1973), 500-525.

[29] Robin J. Wilson, Graph Theory, Fourth Edition, Addison Wesley Longman Limited, Harlow, Essex, UK, 1996.

Top of page