Joseph E. Bonin

Ph.D., Dartmouth College, 1989

Address:

   Joseph E. Bonin
   Department of Mathematics
   Monroe Hall, Room 270
   The George Washington University
   2115 G Street, NW
   Washington, DC, 20052        Phone: (202) 994-6273
       Fax: (202) 994-6760
       e-mail: jbonin@gwu.edu

                    Photo

Contents:
Research Interests Expository Papers Research Publications
Slides of Recent Talks Ph.D. Students

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.

Expository Papers

You can download a brief introduction to matroid theory (35 pages, in postscript; 2001). This is intended as a gentle introduction to the parts of matroid theory that connect most closely with some of my work; this is not a representative survey of the entire field.
You can also download an introduction to extremal matroid theory with an emphasis on the geometric perspective . (75 pages, in postscript.) This document contains the notes for a short course in extremal matroid (Universitat Politecnica de Catalunya, Barcelona, Spring 2003).
You can also download an introduction to transversal matroids. (27 pages, in pdf format; 2010.)

Research Publications

J. Bonin, Basis-exchange properties of sparse paving matroids, Advances in Applied Mathematics, to appear.
J. Bonin, A note on the sticky matroid conjecture, Annals of Combinatorics, 15 (2011) 619-624.
J. Bonin and W. Schmitt, Splicing matroids, European Journal of Combinatorics, Special Issue in Memory of Thomas Brylawski, 32 (2011) 722-744.
J. Bonin, J. P. S. Kung, and A. de Mier, Characterizations of transversal and fundamental transversal matroids, The Electronic Journal of Combinatorics, May 8, 2011.
J. Bonin, A construction of infinite sets of intertwines for pairs of matroids, SIAM Journal on Discrete Mathematics, 24 (2010) 1742-1752.
J. Bonin, Lattice path matroids: the excluded minors, Journal of Combinatorial Theory Series B, 100 (2010) 585-599.
J. Bonin, R. Chen, and K. Xiang, Amalgams of extremal matroids with no U_2,l+2-minor, Discrete Mathematics, 310 (2010) 2317-2322.
J. Bonin and A. de Mier, The lattice of cyclic flats of a matroid, Annals of Combinatorics, 12 (2008) 155-170.
J. Bonin, Transversal lattices, The Electronic Journal of Combinatorics, January 14, 2008.
J. Bonin and O. Gimenez, Multi-path matroids, Combinatorics, Probability, and Computing, 16 (2007) 193-217.
J. Bonin, Extending a matroid by a cocircuit, Discrete Mathematics, 306 (2006) 812-819.
J. Bonin and A. de Mier, Lattice path matroids: Structural properties, European Journal of Combinatorics, 27 (2006) 701-738.
J. Bonin and A. de Mier, Tutte polynomials of generalized parallel connections, Advances in Applied Mathematics, 32 (2004) 31-43.
J. Bonin and A. de Mier, T-uniqueness of some families of k-chordal matroids, Advances in Applied Mathematics, 32 (2004) 10-30.
J. Bonin, A. de Mier, and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, Journal of Combinatorial Theory, Series A, 104 (2003) 63--94.
J. Bonin, Strongly inequivalent representations and Tutte polynomials of matroids, Algebra Universalis, Special Issue in Memory of Gian-Carlo Rota, 49 (2003) 289-303.
R. M. Ankney and J. Bonin, Characterizations of PG(n-1,q)\PG(k-1,q) by numerical and polynomial invariants, Advances in Applied Mathematics, Special Issue in Memory of Rodica Simion, 28 (2002) 287-301.
J. Bonin and H. Qin, Tutte polynomials of q-cones, Discrete Mathematics, 232 (2001) 95-103.
J. Bonin and T. J. Reid, Simple matroids with bounded cocircuit size, Combinatorics, Probability, and Computing, 9 (2000) 407-419.
J. Bonin, Involutions of connected binary matroids, Combinatorics, Probability, and Computing, 9 (2000) 305-308.
J. Bonin and H. Qin, Size functions of subgeometry-closed classes of representable combinatorial geometries, Discrete Mathematics, 224 (2000) 37-60.
J. Bonin and W. P. Miller, Characterizing combinatorial geometries by numerical invariants, European Journal of Combinatorics, 20 (1999) 713-724.
J. Bonin, J. McNulty, and T. J. Reid, The matroid Ramsey number n(6,6), Combinatorics, Probability, and Computing, 8 (1999) 229-235.
J. Bonin, On basis-exchange properties for matroids, Discrete Mathematics, 187 (1998) 265-268.
J. Bonin and J. P. S. Kung, The number of points in a combinatorial geometry with no 8-point-line minor, in: Mathematical Essays in Honor of Gian-Carlo Rota, B. Sagan and R. Stanley, eds., Birkhauser, 1998, 271-284.
J. Bonin, Matroids with no (q+2)-point-line minors, Advances in Applied Mathematics, 17 (1996) 460-476.
K. P. Bogart, J. Bonin, and J. Mittas, Interval orders based on weak orders, Discrete Applied Mathematics, 60 (1995) 93-98.
J. Bonin, Automorphisms of Dowling lattices and related geometries, Combinatorics, Probability, and Computing, 4 (1995) 1-9.
J. Bonin and J. P. S. Kung, Every group is the automorphism group of a rank-3 matroid, Geometriae Dedicata, 50 (1994) 243-246.
R. D. Baker, J. Bonin, F. Lazebnik, and E. Shustin, On the number of nowhere zero points in linear mappings, Combinatorica, 14 (1994) 149-157.
M. K. Bennett, K. P. Bogart, and J. Bonin, The geometry of Dowling lattices, Advances in Mathematics, 103 (1994) 131-161.
J. Bonin, Modular elements of higher-weight Dowling lattices, Discrete Mathematics, 119 (1993) 3-11.
J. Bonin, Automorphism groups of higher-weight Dowling geometries, Journal of Combinatorial Theory, Series B, 58 (1993) 161-173.
J. Bonin, L. Shapiro, and R. Simion, Some q-analogs of the Schroeder numbers arising from combinatorial statistics on lattice paths, Journal of Statistical Planning and Inference, 34 (1993) 35-55.
J. Bonin and K. P. Bogart, A geometric characterization of Dowling lattices, Journal of Combinatorial Theory, Series A, 56 (1991) 195-202.

Slides of Recent Talks

Characterizations of Fundamental Transversal Matroids. (AMS Special Session, New Orleans, January 2011.)
An Introduction to Transversal Matroids. (MAA Short Course, New Orleans, January 2011; see also item 3 under Expository Papers.)
The Excluded Minors of Lattice Path Matroids. (Second Workshop on Graphs and Matroids, Maastricht, The Netherlands, August 2010; Special Session on Algebraic and Geometric Aspects of Matroids, AMS Meeting, Wake Forest University, NC, September 2011.)
Cyclic Flats, Sticky Matroids, and Intertwines. (Workshop on Invariant Theory and Combinatorics, George Mason University, March 2010; Combinatorics Seminar, Universitat Politecnica de Catalunya, Barcelona, Spain, April 2010.)
A Construction of Infinite Sets of Intertwines for Pairs of Matroids. (AMS Meeting, Lexington KY, March 2010; SIAM Meeting, Austin TX, June 2010.)
An Introduction to Matroid Theory Through Lattice Paths. (Colloquium, Howard University, February 2011, The College of William and Mary, April 2011.)
Recent Progress on the Sticky Matroid Conjecture (with a brief introduction to matroid theory). (Combinatorics Seminar, GWU, October 2010.)
What do lattice paths have to do with matrices, and what is beyond both?. (Undergraduate Colloquium, Gettysburg College, November 2010.)

Ph.D. Students

William P. Miller, Approaches to Matroid Reconstruction Problems, 1995.

Hongxun Qin, Tutte Polynomials and Matroid Constructions, 2000.

Rachelle Ankney, The Geometries PG(n-1,q)\PG(k-1,q), 2001.

Updated 14 November 2011.