Oriented cobicircular matroids are GSP Guzmán-Pro, Santiago; Hochstättler, Winfried
Discrete mathematics,
January 2024, 2024-01-00, Volume:
347, Issue:
1
Journal Article
Peer reviewed
Open access
Colourings and flows are well-known dual notions in graph theory. In turn, the definition of flows in graphs naturally extends to flows in oriented matroids. So, the colour-flow duality gives a ...generalization of Hadwiger's conjecture about graph colourings, to a conjecture about coflows of oriented matroids. The first non-trivial case of Hadwiger's conjecture for oriented matroids reads as follows. If O is an M(K4)-minor free oriented matroid, then O has a nowhere-zero 3-coflow, i.e., it is 3-colourable in the sense of Hochstättler-Nešetřil. The class of generalized series parallel (GSP) oriented matroids is a class of 3-colourable oriented matroids with no M(K4)-minor. So far, the only technique towards proving that all orientations of a class C of M(K4)-minor free matroids are GSP (and thus 3-colourable), has been to show that every matroid in C has a positive coline. Towards proving Hadwiger's conjecture for the class of gammoids, Goddyn, Hochstättler, and Neudauer conjectured that every gammoid has a positive coline. In this work we disprove this conjecture by showing that there are infinitely many strict gammoids that do not have positive colines. We conclude by proposing a simpler technique for showing that certain oriented matroids are GSP. In particular, we recover that oriented lattice path matroids are GSP, and we show that oriented cobicircular matroids are GSP.
The separation theorem of Kirchberger can be proven using a combination of Farkas' Lemma and Carathéodory's Theorem. Since those theorems are at the heart of oriented matroids, we are interested in a ...generalization of Kirchberger's Theorem to them. This has already been done for rank 3 oriented matroids. Here we prove it for complexes of oriented matroids, which are a generalization of oriented matroids.
We give two graph theoretical characterizations of tope graphs of (complexes of) oriented matroids. The first is in terms of excluded partial cube minors, the second is that all antipodal subgraphs ...are gated. A direct consequence is a third characterization in terms of zone graphs of tope graphs. Further corollaries include a characterization of topes of oriented matroids due to da Silva, another one of Handa, a characterization of lopsided systems due to Lawrence, and an intrinsic characterization of tope graphs of affine oriented matroids. Moreover, we obtain purely graph theoretic polynomial time recognition algorithms for tope graphs of the above and a finite list of excluded partial cube minors for the bounded rank case. In particular, our results answer a relatively long-standing open question in oriented matroids and can be seen as identifying the theory of (complexes of) oriented matroids as a part of metric graph theory. Another consequence is that all finite Pasch graphs are tope graphs of complexes of oriented matroids, which confirms a conjecture of Chepoi and the two authors.
Orientations of golden-mean matroids Robbins, Jakayla; Slilaty, Daniel
Journal of combinatorial theory. Series B,
September 2023, 2023-09-00, Volume:
162
Journal Article
Peer reviewed
Bland and Las Vergnas proved that orientations of binary matroids are induced by totally unimodular representations. (A related result is due to Minty.) Lee and Scobee proved that orientations of ...ternary matroids are induced by dyadic representations. In this paper we prove that consistently ordered orientations of quaternary matroids are induced by golden-mean representations.
Abstract
We initiate the axiomatic study of affine oriented matroids (AOMs) on arbitrary ground sets, obtaining fundamental notions such as minors, reorientations and a natural embedding into the ...frame work of Complexes of Oriented Matroids. The restriction to the finitary case (FAOMs) allows us to study tope graphs and covector posets, as well as to view FAOMs as oriented finitary semimatroids. We show shellability of FAOMs and single out the FAOMs that are affinely homeomorphic to
$$\mathbb {R}^n$$
R
n
. Finally, we study group actions on AOMs, whose quotients in the case of FAOMs are a stepping stone towards a general theory of affine and toric pseudoarrangements. Our results include applications of the multiplicity Tutte polynomial of group actions of semimatroids, generalizing enumerative properties of toric arrangements to a combinatorially defined class of arrangements of submanifolds. This answers partially a question by Ehrenborg and Readdy.
We show that the topes of a complex of oriented matroids (abbreviated COM) of VC-dimension d admit a proper labeled sample compression scheme of size d. This considerably extends results of Moran and ...Warmuth on ample classes, of Ben-David and Litman on affine arrangements of hyperplanes, and of the authors on complexes of uniform oriented matroids, and is a step towards the sample compression conjecture – one of the oldest open problems in computational learning theory. On the one hand, our approach exploits the rich combinatorial cell structure of COMs via oriented matroid theory. On the other hand, viewing tope graphs of COMs as partial cubes creates a fruitful link to metric graph theory.
Trianguloids and triangulations of root polytopes Galashin, Pavel; Nenashev, Gleb; Postnikov, Alexander
Journal of combinatorial theory. Series A,
January 2024, 2024-01-00, Volume:
201
Journal Article
Peer reviewed
Open access
Triangulations of a product of two simplices and, more generally, of root polytopes are closely related to Gelfand-Kapranov-Zelevinsky's theory of discriminants, to tropical geometry, tropical ...oriented matroids, and to generalized permutohedra. We introduce a new approach to these objects, identifying a triangulation of a root polytope with a certain bijection between lattice points of two generalized permutohedra. In order to study such bijections, we define trianguloids as edge-colored graphs satisfying simple local axioms. We prove that trianguloids are in bijection with triangulations of root polytopes.
PDF
