Wednesday, December 4, 2013 - 4:10pm - 5:30pm
Pardee 217
Dillon Mayhew and Stefan van Zwam, Princeton University
Dillon Mayhew

Title: Fragile matroids and excluded minors

Abstract: Matroid are abstractions of different notions of (in)dependence, in the same way that topologies can be seen as abstractions of different notions of continuity. Matroids are the tools that we use to understand the dependence properties of discrete sets of points in space. We can derive matroids using linear (in)dependence: every matrix over a field gives rise to a matroid, and every matroid that arises in this way is said to be representable. The original motivating problem in matroid theory is to understand the difference between representable and non-representable matroids. This problem has motivated much of the work in matroid theory. The classical way to characterize a class of representable matroids is to use an excluded-minor theorem. These theorems are analogues of the Kuratowski-Wagner theorem, which characterizes planar graphs via excluded minors. This talk will describe our strategy for finding new excluded-minor theorems, which hinges upon matroids with a property called fragility.  This will be an introductory talk: knowledge of matroid theory will not be assumed.


Stefan van Zwam
Title: Connectivity in Graphs and Matroids

Abstract:  A recurring theme in graph theory and its generalizations is connectivity. Menger's Theorem relates two views on connectivity: the maximum number of disjoint paths between vertex sets S and T equals the minimum size of a vertex cut separating S from T. In this talk I will discuss a variant of Menger's Theorem involving two pairs of sets. I will also discuss the generalization to matroids, and several related problems.

Sponsored by: 
Mathematics Department

Contact information

c. jayne trent