Local equivalence of transversals in matroids

D. Fon-Der-Flaass

Abstract


Given any system of $n$ subsets in a matroid $M$, a transversal of this system is an $n$-tuple of elements of $M$, one from each set, which is independent. Two transversals differing by exactly one element are adjacent, and two transversals connected by a sequence of adjacencies are locally equivalent, the distance between them being the minimum number of adjacencies in such a sequence.

We give two sufficient conditions for all transversals of a set system to be locally equivalent. Also we propose a conjecture that the distance between any two locally equivalent transversals can be bounded by a function of $n$ only, and provide an example showing that such function, if it exists, must grow at least exponentially.


Full Text: PDF