Professor of Mathematics
Ph.D., Dartmouth College, 1989
2009 Winner, Oscar and Shoshana Trachtenberg Prize for Teaching Excellence
Member, GW Academy of Distinguished Teachers
MathSciNet, SCOPUS, ResearcherID, and ORCID pages.
|Joseph E. Bonin
Department of Mathematics
Phillips Hall, Room 720A
The George Washington University
801 22nd Street, NW
Washington, DC, 20052
| Phone: (202) 994-6273
Fax: (202) 994-6760
e-mail: jbonin x gwu.edu (where x is the at symbol)
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.
- You can download a brief introduction to matroid theory (35 pages; 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.) 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.)
- J. Bonin, C. Chun, and S. Noble, Delta-matroids as subsystems of sequences of Higgs lifts, Advances in Applied Mathematics, to appear.
- J. Bonin, C. Chun, and S. Noble, The excluded 3-minors for vf-safe delta-matroids, Advances in Applied Mathematics, to appear.
- J. Bonin and J.P.S.Kung, The G-invariant and catenary data of a matroid, Advances in Applied Mathematics, 94 (2018) 39-70.
- J. Bonin, Lattices related to extensions of presentations of transversal matroids, The Electronic Journal of Combinatorics, March 17, 2017.
- J. Bonin and T. Savitsky, An infinite family of excluded minors for strong base-orderability, Linear Algebra and its Applications, 488 (2016) 396-429.
- J. Bonin and A. de Mier, Extensions and presentations of transversal matroids, European Journal of Combinatorics, Special Issue in Memory of Michel Las Vergnas, 50 (2015) 18-29.
- J. Bonin and J. P. S. Kung, Semidirect sums of matroids, Annals of Combinatorics, 19 (2015) 7-27.
- J. Bonin, Basis-exchange properties of sparse paving matroids, Advances in Applied Mathematics, 50 (2013) 6-15.
- 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 U2,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.
J. Bonin and C. Chun, Decomposable polymatroids and connections with graph coloring
- New Connections between Polymatroids and Graph Coloring. (CanaDAM 2019, Simon Fraser University, Vancouver.) (Version for Louisiana State University.)
- Delta-matroids as subsystems of sequences of Higgs lifts, or a way to think about delta-matroids from the perspective of matroids. (PRIMA 2017, Oaxaca, Mexico, August 2017.) Combinatorial Geometries 2018, Marseille, France, CIRM, September 2018
Video of the CIRM talk.
- Minor-Closed Classes of Polymatroids. (CanaDAM, Toronto, June 2017.) (GW Seminar Version.) (AMS Sectional Meeting, Vanderbilt University.)
- A New Perspective on the G-Invariant of a Matroid. (2016 International Workshop on Structure in Graphs and Matroids, Eindhoven, The Netherlands; George Mason University, Combinatorics, Algebra, and Geometry Seminar, October 2016.)
University of Delaware Combinatorics Seminar Version
Combinatorics Seminar, Louisiana State University, November 2018
- Lattice Path Matroids, Tutte Polynomials, and the G-Invariant. (Colloquium, U.S. Naval Academy, 2016.)
- Cyclic flats of matroids and their connections to Tutte polynomials and other matroid invariants. (Workshop on New Directions for the Tutte Polynomial: Extensions, Interrelations, and Applications, Royal Holloway University of London, July 2015.)
- Excluded Minors for (Strongly) Base Orderable Matroids. (CanaDAM, Saskatoon, June 2015.)
- Presentations and Extensions of Transversal Matroids. (2014 International Workshop on Structure in Graphs and Matroids, Princeton University, July 2014.)
- Semidirect Sums of Matroids. (Third Workshop on Graphs and Matroids, Maastricht, The Netherlands, August 2012.)
- Characterizations of Fundamental Transversal Matroids. (AMS Special Session, New Orleans, January 2011.)
- An Introduction to Transversal Matroids. (MAA Short Course, New Orleans, January 2011.)
- 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, Wichita State University, November 2009. Colloquium, Howard University, February 2011, The College of William and Mary, April 2011. Discrete Math Seminar, Virginia Commonwealth University, March 2016.)
- Recent Progress on the Sticky Matroid Conjecture (with a brief introduction to matroid theory). (Combinatorics Seminar, GWU, October 2010.)
- Old and new connections between matroids and codes: a short introduction to two fields. (Graduate Colloquium, Louisiana State University, November 2018.)
- What do lattice paths have to do with matrices, and what is beyond both?. (Undergraduate Colloquium, Gettysburg College, November 2010. Undergraduate Colloquium, U.S. Naval Academy, April 2016.)
- 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.
- Ken Shoda, Large Families of Matroids with the Same Tutte Polynomial, 2012.
- Thomas Savitsky, Some Problems on Matroids and Integer Polymatroids, 2015.