Péter Ágoston ; Gábor Damásdi ; Balázs Keszegh ; Dömötör Pálvölgyi - Orientation of good covers

dmtcs:15019 - Discrete Mathematics & Theoretical Computer Science, September 10, 2025, vol. 27:3 - https://doi.org/10.46298/dmtcs.15019
Orientation of good coversArticle

Authors: Péter Ágoston ; Gábor Damásdi ; Balázs Keszegh ; Dömötör Pálvölgyi

    We study systems of orientations on triples that satisfy the following so-called interiority condition: $\circlearrowleft(ABD)=~\circlearrowleft(BCD)=~\circlearrowleft(CAD)=1$ implies $\circlearrowleft(ABC)=1$ for any $A,B,C,D$. We call such an orientation a P3O (partial 3-order), a natural generalization of a poset, that has several interesting special cases. For example, the order type of a planar point set (that can have collinear triples) is a P3O; we denote a P3O realizable by points as p-P3O. If we do not allow $\circlearrowleft(ABC)=0$, we obtain a T3O (total 3-order). Contrary to linear orders, a T3O can have a rich structure. A T3O realizable by points, a p-T3O, is the order type of a point set in general position. In our paper "Orientation of convex sets" we defined a 3-order on pairwise intersecting convex sets; such a P3O is called a C-P3O. In this paper we extend this 3-order to pairwise intersecting good covers; such a P3O is called a GC-P3O. If we do not allow $\circlearrowleft(ABC)=0$, we obtain a C-T3O and a GC-T3O, respectively. The main result of this paper is that there is a p-T3O that is not a GC-T3O, implying also that it is not a C-T3O -- this latter problem was left open in our earlier paper. Our proof involves several combinatorial and geometric observations that can be of independent interest. Along the way, we define several further special families of GC-T3O's.


    Volume: vol. 27:3
    Section: Combinatorics
    Published on: September 10, 2025
    Accepted on: June 30, 2025
    Submitted on: January 3, 2025
    Keywords: Combinatorics, 52C99

    Consultation statistics

    This page has been seen 476 times.
    This article's PDF has been downloaded 277 times.