Tag Archives: online talks

Online Talk: Jagdeep Singh

Posted on by
Reply

Tuesday, Oct 5, 3pm ET (8pm BST, 8am Wed NZST)
Jagdeep Singh, Louisiana State University
$2$-Cographs and Binary Comatroids

 
Abstract:
The well-known class of cographs or complement-reducible graphs is the class of graphs that can be generated from $K_1$ using the operations of disjoint union and complementation. In this talk, we consider $2$-cographs, a natural generalization of cographs, and binary comatroids, a matroid analogue. We show that, as with cographs, both $2$-cographs and binary comatroids can be recursively defined. However, unlike cographs, $2$-cographs and binary comatroids are closed under induced minors. We consider the class of non-$2$-cographs for which every proper induced minor is a $2$-cograph and show that this class is infinite. Our main result for graphs finds the finitely many members of this class whose complements are also  induced-minor-minimal non-$2$-cographs. In the matroid case, our main result identifies all binary non-comatroids for which every proper flat is a binary comatroid. This is joint work with James Oxley.

 

Online Talk: Jim Geelen

Posted on by
Reply

Tuesday, Sept 28, 3pm ET (8pm BST, 8am Wed NZST)
Jim Geelen, University of Waterloo
Is this Ramsey’s Theorem for Matroids?

 
Abstract:
For a simple matroid $M$ with no lines of length $l$ or more, if the rank of $M$ is sufficiently large (as a function of $l$) and we $2$-colour the elements of $M$, is there necessarily a monochromatic line? We discuss this and a good many related problems.

 

Online Talk: Evelyne Smith-Roberge

Posted on by
Reply

Tuesday, Sept 14, 3pm ET (8pm BST, 7am Wed NZST)
Evelyne Smith-Roberge, University of Waterloo
A local choosability theorem for planar graphs

 
Abstract:
Two famous theorems of Thomassen show that every planar graph is 5-choosable, and that every planar graph of girth at least five is 3-choosable. These theorems are best possible for uniform list assignments: Voigt gave a construction of a planar graph that is not 4-choosable, and of a planar graph of girth four that is not 3-choosable. In this talk, I will introduce the concept of a local girth list assignment: a list assignment wherein the list size of each vertex depends not on the girth of the graph, but only on the length of the shortest cycle in which the vertex itself is contained. I will present a local choosability theorem for planar graphs that unifies the two theorems of Thomassen mentioned above. Joint work with Luke Postle.