Title: Discovery of the Trellis
| Speaker: | Nishad Kothari |
| Affiliation: | Combinatorics & Optimization, University of Waterloo |
| Room: | MC 5501 |
Abstract:
A brick is a 3-connected graph with the additional property that deleting any two vertices results in a graph which has a perfect matching. Bricks play a central role in matching theory.
As per a theorem of Lovasz (1983), every brick either "contains" K4, or it "contains" the triangular prism (or both). A brick is K4-free if it does not contain K4.
In a joint work with Murty (published in 2016), we proved that a planar brick is K4-free if and only if it has precisely two odd faces.
Having characterized planar K4-free bricks, in March 2013, I (falsely) conjectured that there does not exist any nonplanar K4-free brick.
Roughly seven months later, on the fateful night of October 26th, I ran into a counterexample to this conjecture, the Trellis (as named later by Murty). The Trellis is a cubic graph on 14 vertices, and it happens to be the smallest counterexample.
In this talk, I will describe our beautiful journey which led to the discovery of the Trellis, and I will discuss other fascinating properties of the Trellis.