A note on embracing exchange sequences in oriented matroids
By: Kristóf Bérczi, Benedek Nádor
Potential Business Impact:
Finds faster ways to change shapes while keeping a center point.
An open problem in convex geometry asks whether two simplices $A,B\subseteq\mathbb{R}^d$, both containing the origin in their convex hulls, admit a polynomial-length sequence of vertex exchanges transforming $A$ into $B$ while maintaining the origin in the convex hull throughout. We propose a matroidal generalization of the problem to oriented matroids, concerning exchange sequences between bases under sign constraints on elements appearing in certain fundamental circuits. We formulate a conjecture on the minimum length of such a sequence, and prove it for oriented graphic matroids of directed graphs. We also study connections between our conjecture and several long-standing open problems on exchange sequences between pairs of bases in unoriented matroids.
Similar Papers
A note on embracing exchange sequences in oriented matroids
Combinatorics
Finds shortest path between geometric shapes.
Arithmetic Circuits and Neural Networks for Regular Matroids
Combinatorics
Finds best ways to pick items for matroids.
Prefix-bounded matrices
Combinatorics
Makes math puzzles about grids easier to solve.