A note on embracing exchange sequences in oriented matroids

Kristóf Bérczi, Benedek Nádor · 2025

Read A note on embracing exchange sequences in oriented matroids by Kristóf Bérczi, Benedek Nádor (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14526.txt.

Introduction

Kristóf Bérczi and Benedek Nádor study exchange sequences in oriented matroids, motivated by a geometry puzzle. The puzzle asks whether two simplices that both cover the origin can be turned into each other by short vertex swaps. Each swap must keep the origin covered. The authors lift the question to oriented matroids with sign rules on key circuits.

They state a conjecture for the shortest such exchange sequence. They prove it for oriented graphic matroids that come from directed graphs. They also link their conjecture to several long standing open problems on basis exchanges. The note frames a broad problem in a clean combinatorial form.

Catalog record

CREATORKristóf Bérczi, Benedek Nádor
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14526

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A note on embracing exchange sequences in oriented matroids Kristóf Bérczi, Benedek Nádor Abstract An open problem in convex geometry asks whether two simplices A , B ⊆ ℝ d A,B\subseteq\mathbb{R}^{d} , both containing the origin in their convex hulls, admit a polynomial-length sequence of vertex exchanges transforming A A into B 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. Keywords: Carathéodory theorem, Directed graphs, Exchange sequences, Matroids, Oriented matroids 1 Introduction Carathéodory’s theorem [ 5 ] is a cornerstone of convex geometry, describing how points in a convex hull can be represented. It states that if a point x lies in the convex hull of a set P\subseteq\mathbb{R}^{d} , then there exists a subset of at most d+1 points of P whose convex hull already contains x . In other words, every point in a convex hull admits a sparse representation, with the bound d+1 being best possible. A fundamental extension of this classical result is the Colorful Carathéodory theorem, introduced by Bárány [ 2 ] . In this setting, one is given d+1 point sets, called color classes, each containing the origin in its convex hull. The theorem guarantees that one can select a single point from each color class so that the origin lies in the convex hull of the d+1 chosen points. Equivalently, the colorful version ensures the existence of a “rainbow” simplex embracing the origin. Both the classical and colorful Carathéodory theorems have played a central role in combinatorial geometry, optimization, and matroid theory, and continue to motivate algorithmic and structural questions. From an algorithmic point of view, there is a significant difference between the classical and the colorful variants. The classical theorem can be realized using standard linear programming: a basic feasible solution of the corresponding linear system yields a convex combination involving at most d+1 points in polynomial time. In contrast, constructive proofs of the colorful variant rely on iterative linear programming steps, and no strongly polynomial-time algorithm is known for the general case, although special cases and approximate variants admit more efficient procedures; we refer the interested reader to [ 10 ] for further details. A natural relaxation of this problem arises when there are only k<d+1 point sets, and the goal is to find a colourful set containing, for each i\in[k] , d_{i} points from the i -th set. When k=2 and the target sizes (d_{1},d_{2}) satisfy d_{1}+d_{2}=d+1 , the problem admits a polynomial-time solution, as shown by Meunier, Mulzer, Sarrabezolles, and Stein [ 9 ] . In an effort to better understand this 2-colour case and to explore the possibility of extending polynomial-time algorithms to higher numbers of colours, Caoduro, Khodamoradi, Paat, and Shepherd [ 4 ] raised the following problem: Given two 0-embracing sets A,B\subseteq\mathbb{R}^{d} , that is, sets whose convex hulls contain the origin, is it always possible to transform A into B by a polynomial-length sequence of exchanges, where each step replaces a point of the current set with a point from A\cup B and every intermediate set remains 0-embracing? We call the minimum number of such exchanges the 0 -embracing exchange distance of A and B . To see this, form a (d+1)\times(2d+2) matrix M whose columns are the coordinates of the points in A\cup B , augmented by an additional row consisting entirely of 1 ’s. Let b\in\mathbb{R}^{d+1} be the vector whose first d entries are 0 and whose last entry is 1 . Each exchange of a point in A with a point in B can then be interpreted as traversing an edge of the polyhedron P=\{x\in\mathbb{R}^{2d+2}\mid Mx=b,;x\geq 0\} . Therefore, if G denotes the 1 -skeleton of P , then following a path in G yields a sequence of exchanges in which, at each step, one point is removed from the current simplex and replaced by another point from A\cup B , while preserving the property that the origin lies in the convex hull. Based on computational experiments, Caoduro, Khodamoradi, Paat, and Shepherd [ 4 ] proposed the following conjecture. Conjecture 1.1 (Caoduro, Khodamoradi, Paat, Shepherd) . The 0 -embracing exchange distance of two 0 -embracing d -dimensional simplices is at most d+1 . Although the Hirsch conjecture is now known to be false in general, Conjecture 1.1 would follow from its original formulation (see [ 7 ] ), since the polyhedron P has 2d+2 facets and dimension 2d+2-(d+1)=d+1 . Consequently, the Hirsch bound would guarantee the existence of a path of length at most d+1 between the corresponding vertices in the 1 -skeleton of P . Conjecture 1.1 remains open. The problem, however, resembles several long-standing conjectures concerning the symmetric exchange distance of basis-pairs in matroids, such as those proposed by Gabow [ 8 ] , White [ 11 ] , and Hamidoune [ 6 ] ; see Section 3 for details. This observation naturally suggests that the problem may, in fact, be a special case of a more general, abstract question concerning matroids. 1.1 Basic notation General notation. For integers k and \ell with k\leq\ell , we write [k,\ell]={k,k+1,\dots,\ell} ; when k=1 , we simply write [\ell]=[1,\ell] . Given a ground set S , a set X\subseteq S and an element y\in S , the sets X\setminus\{y\} and X\cup\{y\} are often abbreviated as X-y and X+y , respectively. Oriented matroids. For basic definitions on oriented matroids, we refer to [ 3 ] . An oriented matroid M=(E,\mathcal{C}) on a finite ground set E can be defined via its collection \mathcal{C} of signed circuits , where each C\in\mathcal{C} is a pair (C^{+},C^{-}) of disjoint subsets of E representing the elements with positive and negative signs, respectively, satisfying the following axioms. (C1) Nontriviality: \emptyset\notin\mathcal{C} . (C2) Symmetry: If C\in\mathcal{C} , then -C=(C^{-},C^{+})\in\mathcal{C} . (C3) Incomparability: If C_{1},C_{2}\in\mathcal{C} and C_{1}\subseteq C_{2} , then C_{1}=C_{2} or C_{1}=-C_{2} . (C4) Circuit elimination: If C_{1},C_{2}\in\mathcal{C} , C_{1}\neq-C_{2} , and e\in C_{1}^{+}\cap C_{2}^{-} , then there exists C_{3}\in\mathcal{C} such that C_{3}^{+}\subseteq(C_{1}^{+}\cup C_{2}^{+})-e and C_{3}^{-}\subseteq(C_{1}^{-}\cup C_{2}^{-})-e . The circuit family of the underlying unoriented matroid \underline{M} is obtained by ignoring the signs of the circuits. A basis of M is a basis of \underline{M} , and the fundamental circuit of e\notin B with respect to a basis B is the unique circuit of \underline{M} contained in B+e . Given a basis B and an element e\in E\setminus B , let C(B,e) denote the signed fundamental circuit of e with respect to B , oriented so that e has negative sign; we call this the anchored fundamental circuit of e with respect to B . A basis B is e -embracing if, in the anchored fundamental circuit of e with respect to B , every element distinct from e is positive. For two e -embracing bases A and B , a sequence of bases A=T_{0},T_{1},\dots,T_{q-1},T_{q}=B is an e

Read the complete text