Twenty minutes before the talk coffee and cookies will be available in
Bear Hall 211.
Title: Circuits and Cocircuits in Matroids.
Speaker: Nolan McMurray
Abstract:
Scott Smith conjectured in 1979 that distinct longest cycles of a k-connected
graph meet in at least k vertices when k greater than
or equal to 2. This conjecture is still open. Reid and Wu
generalized the conjecture to matroids by considering largest
circuits. An equivalent conjecture in terms of largest cocircuits
is given here. The specialization of this conjecture to graphs is
then obtained. This specialization involves largest bonds in a
graph.
The general conjecture about largest circuits in a k-connected matroid
was solved by Seymour for the case k = 2. We provide an
attractive generalization of this result for circuits that are almost
largest circuits. In addition, we prove the general conjecture
for the class of uniform matroids and the class of matroids with
larges circuit size at most four. The main result of this
work establishes the general conjecture
for k-connected cographic matroids when k less than or
equal
to 5. This provides a dual result to the establishment of Smith's
conjecture
for k less than or equal to 10 as reported by Grotschel.
Several related results on largest bonds in graphs are also given.