Research Interests
My primary research interest is matroid theory, which is a branch
of combinatorics. Matroid theory was founded in the 1930's by Hassler
Whitney, who noticed a common thread in certain ideas of independence
in linear algebra and graph theory. The two-way interplay between
matroid theory and its many fields of application yields a rich and
powerful theory. At a basic level, linear algebra contributes the
ideas of flats (generalizing subspaces) and rank (generalizing
dimension); graph theory contributes the ideas of circuits and
cocircuits (the latter generalizing minimal edge cut-sets). Flats and
rank are then new tools for exploring graphs; circuits and cocircuits
shed light on linear independence. As one pursues the field further,
and as one exploits the simple but powerful idea of matroid duality,
this interplay gets rich and deep.
The 1960's and 70's witnessed an explosive growth in the field,
spurred partly by newly discovered connections with optimization: for
instance, matroids are the simplicial complexes on which the greedy
algorithm yields optimal solutions. Matroid theory also has important
connections with coding theory, arrangements of hyperplanes, the
rigidity of bar and joint frameworks, knot theory, and many other
areas.
My work in matroid theory has spanned a fair number of facets of
the field, including the following.
- Dowling lattices are roughly to groups what projective
geometries (essentially, lattices of subspaces of a vector space) are
to fields. Dowling lattices were one of my first topics of research
(indeed, they induced me to pursue matroid theory) and I have returned
to these attractive matroids many times.
- The critical problem forms the theoretical framework for
numerous important problems, including Tutte's 5-flow conjecture and
Hadwiger's conjecture. The problem is roughly to determine the
minimal number of affine submatroids into which we can partition a
given matroid that is representable over a fixed finite field. The
critical problem connects certain Dowling lattices with the
fundamental problem of linear coding theory.
- Two typical generic questions in extremal matroid theory
are: How many elements can a matroid have, given certain side
conditions? and, more generally, Are there inequalities that
relate various parameters of a matroid? Some especially attractive
matroids (e.g., projective geometries) can be characterized as the
unique example that show the optimality of certain inequalities among
various parameters of a matroid. One problem in extremal matroid
theory that particularly interests me is to determine the maximal
number of cyclic flats that a matroid on a fixed number of elements
can have.
- Associated with a matroid are many polynomials, including the
Tutte polynomial. Tutte polynomials have rightly received
considerable attention due to their many connections with other
fields; specializations of Tutte polynomials include chromatic and
flow polynomials of graphs, weight enumerators of linear codes, and
Jones polynomials of alternating knots. Among the many questions one
can ask in this area are: Which matroids are determined up to
isomorphism by their Tutte polynomial? and, complementary to that,
How can we construct huge families of matroids that have the same
Tutte polynomial?
- Transversal matroids are one of the classes of matroids
that greatly spurred the growth of the field in the 1970's. Although
studied less these days, some appealing aspects of these matroids have
only recently been brought to light. For instance,
lattice path matroids provide an elegant bridge between certain
topics in enumerative combinatorics and special transversal matroids,
and these matroids have many uncommon and attractive properties, such
as having polynomial-time algorithms for computing their Tutte
polynomials and having simple interpretations of basis
activities.
- The lattice of flats provides a well-studied bridge between
matroids and geometric lattices; the lattice of cyclic flats
has been explored much less. In contrast to the lattice of flats,
every finite lattice is isomorphic to the lattice of cyclic
flats of some matroid, indeed of a transversal matroid.
Order-theoretic properties of the cyclic flats provide a new way to
define special classes of matroids, some of which have striking
properties. For instance, matroids in which any two cyclic flats are
comparable under inclusion (nested matroids) provided the first
known example of a minor-closed class of matroids that is
well-quasi-ordered but has infinitely many excluded minors.