Embracing exchange sequences and oriented matroid polyhedron diameter
For researchers in combinatorial optimization and oriented matroid theory, this resolves open conjectures and provides tight bounds for a specific class.
The paper reduces the embracing exchange distance of bases of oriented matroids to the metric of oriented matroid polyhedra, disproving recent conjectures while proving an upper bound of 2r^{log2(r)+3} steps for general oriented matroids and r steps for Lawrence oriented matroids.
We reduce the embracing exchange distance of bases of oriented matroids to the metric of oriented matroid polyhedra. This allows us to disprove recent conjectures of Caoduro, Khodamoradi, Paat, and Shepherd and of Bérczi and Nádor. On the other hand, we show that any two embracing bases of an oriented matroid of rank $r$ can be transformed into each other in at most $2r^{\log_2(r)+3}$ steps and in at most $r$ steps in a Lawrence oriented matroid, thus confirming the conjecture in this case.