Ben Smith

University of Lancaster


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.
css.php