Tuesday, Oct 5, 3pm ET (8pm BST, 8am Wed NZST)
Jagdeep Singh, Louisiana State University
$2$-Cographs and Binary Comatroids
YouTube: https://youtu.be/EVzwtQ0cgOY
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.