Monday, April 12, 3pm ET (8pm BST, 7am Tue NZST)
Daryl Funk, Douglas College
The class of bicircular matroids has only a finite number of excluded minors
We show that the class of bicircular matroids has only a finite number of excluded minors. Key tools used in our proof include representations of matroids by biased graphs and the recently introduced class of quasi-graphic matroids. We show that if $N$ is an excluded minor of rank at least eight, then $N$ is quasi-graphic. Several small excluded minors are quasi-graphic. Using biased-graphic representations, we find that $N$ already contains one of these. We also provide an upper bound, in terms of rank, on the number of elements in an excluded minor, so the result follows.
Monday, April 5, 3pm ET (8pm BST, 7am Tue NZST)
Raphael Steiner, TU Berlin
Directed graphs: Substructures and Coloring
Two popular topics that are classically studied in graph theory are (A) substructures of “dense” graphs and (B) substructures of graphs with large chromatic number. Well-known notions of “substructure” used in this context are (induced) subgraphs, minors, and subdivisions. Unfortunately, interesting generalizations of these concepts to the directed setting, despite being very natural, have received considerably less attentation. In this talk, I want to popularize this topic by surveying some intriguing open problems and known partial results (some of my own) related to the following questions.
(A) Which substructures can be found in digraphs that are very dense? (Meaning that they have large minimum out- and/or in-degree).
(B) Which substructures can be found in digraphs whose dichromatic number is large? (Dichromatic number being an established extension of the chromatic number to directed graphs).
Monday, March 29, 3pm ET (8pm BST, 8am Tue NZDT)
Charles Semple, University of Canterbury
Matroids with wheel- and whirl-like properties
Tutte showed that wheels and whirls are precisely the $3$-connected matroids in which every element is contained in a $3$-element circuit and a $3$-element cocircuit. As a consequence, wheels and whirls are exactly the $3$-connected matroids in which there is a circular ordering of the ground set such that every two consecutive elements is contained in a $3$-element circuit and a $3$-element cocircuit. More recently, Miller proved that sufficiently large (tipless) spikes are precisely the matroids in which every two elements is contained in a $4$-element circuit and a $4$-element cocircuit. In this talk, we investigate matroids satisfying generalisations of these properties and discuss some recent results. This is joint work with Nick Brettell, Deborah Chun, Tara Fife, James Oxley, Simon Pfeil, Gerry Toft, and Geoff Whittle.
Monday, March 22, 3pm ET (7pm GMT, 8am Tue NZDT)
Peter Nelson, University of Waterloo
Like in many areas of mathematics, long and technical proofs in combinatorics are becoming more common. When we consider the refereeing process, the unpleasant screeds of case-analysis with which many of us are familiar, and our high standards for mathematical truth, it is natural to have uncomfortable doubts due to simple human fallibility. A potential panacea is to use proof assistants to formally verify the correctness of our theorems. I will describe efforts I have made in recent months to formalize parts of matroid theory using the lean theorem prover, and a modest few results about matroids that are now formalized, including Edmonds’ Matroid Intersection Theorem. The talk is particularly aimed towards combinatorialists that are curious about this area; I will discuss both the bigger picture as well as the day-to-day experience of using a theorem prover, assuming no prior knowledge. This is joint work with Edward Lee and Mathieu Guay-Paquet.