Serial symmetric exchanges

From Egres Open
Jump to: navigation, search

Let M be a matroid, and let A and B be two bases of M. A subset X of A and a subset Y of B, both of size k, form a serial symmetric exchange with respect to A and B if there is an ordering [math]x_1,\dots,x_k[/math] of X and an ordering [math]y_1,\dots,y_k[/math] of Y such that both [math]A \setminus \{x_1,\dots,x_i\} \cup \{y_1,\dots,y_i\}[/math] and [math]B \setminus \{y_1,\dots,y_i\} \cup \{x_1,\dots,x_i\}[/math] are bases for every [math]i \in \{1,\dots,k\}[/math].

Is it true that for any matroid M, any two bases A and B, and any [math]X \subseteq A[/math], there exists [math]Y \subseteq B[/math] such that X and Y form a serial symmetric exchange with respect to A and B?


Remarks

This conjecture was proposed by Kotlar and Ziv [1]. If true, it would imply the conjecture on Cyclic orderings of matroids for k=2, and the conjecture on Equitability of matroids. Kotlar and Ziv proved that the conjecture is true if [math]|X|=2[/math].

References

  1. D. Kotlar, R. Ziv, On Serial Symmetric Exchanges of Matroid Bases, arXiv link