Joseph E. Bonin

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.