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.

Abstract. Planar bipartite graphs can be represented as touching graphs of horizontal and vertical segments in [Formula: see text]. We study a generalization in space—touching graphs of axis-aligned rectangles in [Formula: see text]—and prove that planar 3-colorable graphs can be represented this way. The result implies a characterization of corner polytopes previously obtained by Eppstein and Mumford. A by-product of our proof is a distributive lattice structure on the set of orthogonal surfaces with given skeleton. Further, we study representations by axis-aligned non-coplanar rectangles in [Formula: see text] such that all regions are boxes. We show that the resulting graphs correspond to octahedrations of an octahedron. This generalizes the correspondence between planar quadrangulations and families of horizontal and vertical segments in [Formula: see text] with the property that all regions are rectangles.

Abstract. Let [Formula: see text] be a finite set. A family [Formula: see text] of subsets of [Formula: see text] is called a convex geometry with ground set [Formula: see text] if (1) [Formula: see text]; (2) [Formula: see text] whenever [Formula: see text]; and (3) if [Formula: see text] and [Formula: see text], there is an element [Formula: see text] such that [Formula: see text]. As a nonempty family of sets, a convex geometry has a well defined [Formula: see text]-dimension. In the literature, a second parameter, called the convex dimension, has been defined expressly for these structures. Partially ordered by inclusion, a convex geometry is also a poset, and four additional dimension parameters have been defined for this larger class, called the Dushnik–Miller dimension, Boolean dimension, local dimension, and fractional dimension, respectively. For each pair of these six dimension parameters, we investigate whether there is an infinite class of convex geometries on which one parameter is bounded and the other is not.

This paper considers completions of tope graphs of complexes of oriented matroids (COMs) to ample partial cubes of the same Vapnik--Chervonenkis dimension (VC-dimension). We show that these exist for oriented matroids (OMs) and complexes of uniform oriented matroids (CUOMs). This implies that tope graphs of OMs and CUOMs satisfy the sample compression conjecture---one of the central open questions of learning theory. We conjecture that the tope graph of every COM can be completed to an ample partial cube without increasing the VC-dimension.

Abstract Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other? We consider flip graphs on orientations of simple graphs, where flips consist of reversing the direction of some edges. More precisely, we consider so-called $$\alpha$$ α -orientations of a graph G, in which every vertex v has a specified outdegree $$\alpha (v)$$ α ( v ) , and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two $$\alpha$$ α -orientations of a planar graph G is at most two is -complete. This also holds in the special case of perfect matchings, where flips involve alternating cycles. This problem amounts to finding geodesics on the common base polytope of two partition matroids, or, alternatively, on an alcoved polytope. It therefore provides an interesting example of a flip distance question that is computationally intractable despite having a natural interpretation as a geodesic on a nicely structured combinatorial polytope. We also consider the dual question of the flip distance between graph orientations in which every cycle has a specified number of forward edges, and a flip is the reversal of all edges in a minimal directed cut. In general, the problem remains hard. However, if we restrict to flips that only change sinks into sources, or vice-versa, then the problem can be solved in polynomial time. Here we exploit the fact that the flip graph is the cover graph of a distributive lattice. This generalizes a recent result from Zhang et al. (Acta Math Sin Engl Ser 35(4):569–576, 2019).

We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer k, every finite set of points in ℝ3 can be colored with k colors so that every translate of the negative octant containing at least k6 points contains at least one of each color. The best previously known bound was doubly exponential in k. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semi-online model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.

We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer $k$, every finite set of points in $\mathbb{R}^3$ can be colored with $k$ colors so that every translate of the negative octant containing at least $k^6$ points contains at least one of each color. The best previously known bound was doubly exponential in $k$. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semionline model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.