k-fold Circuits in Matroids
Combinatorics Seminar
28th January 2025, 11:00 am – 12:00 pm
Fry Building, 2.04
A matroid is a combinatorial object that encodes dependences in structures, such as linear dependences between collections of vectors. One way to define a matroid is via its circuits, the minimal dependent sets. Lovász introduced double circuits in 1980 as a fundamental tool for studying the matroid matching problem, a notable NP-hard problem that generalises a number of problems in combinatorial optimization. Explicitly, he derived a min-max formula for the size of a maximum matching in certain families of matroids. This formula was extended to all matroids satisfying the so-called 'double circuit property' by Dress and Lovász in 1987.
In this talk, we extend the notion of circuits and double circuits to k-fold circuits, sets that encode k dependences, and study their structure. In particular, we show that many families of matroids which are known to satisfy the double circuit property also satisfy the k-fold circuit property. Our results utilise a number of deep ideas from lattice theory, including modularity and identifying modular sublattices.
This is joint work with Bill Jackson and Tony Nixon.
Comments are closed.