Convex geometries and directed paths on three vertices

Júlio Araújo, Mitre C. Dourado, Marisa Gutierrez, Fabio Protti, Silvia Tondato · 2026

Read Convex geometries and directed paths on three vertices by Júlio Araújo, Mitre C. Dourado, Marisa Gutierrez, Fabio Protti, Silvia Tondato (2026) 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-2606-24707.txt.

Introduction

Júlio Araújo and four colleagues work on convexity in oriented graphs. A convexity space pairs a set with a family of subsets called convex, closed under intersections and nested unions. A convexity is geometric when every convex set is the hull of its extreme points. The authors study two convexities built from directed paths on three vertices. In one, a set is convex if no outside vertex centres a directed path with endpoints inside. A starred variant adds a condition on arcs.

Araújo and colleagues give exact conditions on the graph for each convexity to be geometric. For the first convexity, the conditions yield a polynomial time test for geometricity. For the starred one, they prove the same decision problem is coNP hard in general. They then define a family called acyclic indifference oriented graphs. On that family, the starred decision problem becomes polynomial time again.

Catalog record

CREATORJúlio Araújo, Mitre C. Dourado, Marisa Gutierrez, Fabio Protti, Silvia Tondato
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24707

Browse the full library · About the Tower of Babel

Full text

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

Convex geometries and directed paths on three vertices Júlio Araújo, Mitre C. Dourado, Marisa Gutierrez, Fabio Protti, Silvia Tondato Abstract A convexity space is an ordered pair ( V , 𝒞 ) (V,\mathcal{C}) , where V V is an arbitrary set and 𝒞 \mathcal{C} is a family of subsets of V V , called convex sets , which contains { ∅ , V } \{\emptyset,V\} and is closed under intersections and nested unions of its elements. For any S ⊆ V S\subseteq V , the convex hull of S S is the inclusion-wise minimum convex set C ∈ 𝒞 C\in\mathcal{C} such that S ⊆ C S\subseteq C . For a convex set C ∈ 𝒞 C\in\mathcal{C} , an element p ∈ C p\in C is an extreme of C C if p p does not belong to the convex hull of C ∖ { p } C\setminus\{p\} . A convexity 𝒞 \mathcal{C} defined over V V is a convex geometry (a.k.a. geometric convexity ) if any convex set C ∈ 𝒞 C\in\mathcal{C} is the convex hull of its extreme elements. Given an oriented graph D = ( V , A ) D=(V,A) , the family 𝒞 \mathcal{C} of subsets of V V is the P_3 \opthree -convexity defined over D D if 𝒞 \mathcal{C} is formed by all (convex) sets C ⊆ V C\subseteq V satisfying the following property: no vertex v ∈ V ∖ C v\in V\setminus C is the central vertex of a directed path P = ( u , v , w ) P=(u,v,w) with { u , w } ⊆ C \{u,w\}\subseteq C . In the P_3^* \opthrees -convexity defined over D D , we have that 𝒞 \mathcal{C} is formed by all (convex) sets C ⊆ V C\subseteq V satisfying the following property: no vertex v ∈ V ∖ C v\in V\setminus C is the central vertex of a directed path P = ( u , v , w ) P=(u,v,w) such that { u , w } ⊆ C \{u,w\}\subseteq C and ( u , w ) ∉ A (u,w)\notin A . In this work, we present necessary and sufficient conditions over an oriented graph D D so that the P_3 \opthree -convexity over D D is geometric, or the P_3^* \opthrees -convexity over D D is geometric. While the first case implies a polynomial-time algorithm to decide whether the P_3 \opthree -convexity over D D is a geometric, we show that it is 𝖼𝗈𝖭𝖯 {\mathsf{coNP}} to decide whether the P_3^* \opthrees -convexity over D D is a convex geometry. We also present a family of oriented graphs, termed acyclic indifference oriented graph, and demonstrate that deciding whether the P_3^* \opthrees -convexity over an acyclic indifference oriented graph is geometric can be solved in polynomial-time. Keywords: Graph convexity; Oriented graphs ; P_3 \opthree -convexity; P_3^* \opthrees -convexity \usetikzlibrary arrows.meta 1 Introduction For further notions on Graph Theory and Abstract Convexity, the reader is referred to [ BM2008 , vandeVel1993 ] . For an extensive overview of directed graphs, see [ BG2008 ] . In this work, we only consider simple and finite (directed) graphs. A convexity space is an ordered pair (V,\mathcal{C}) , where V is an arbitrary set, and \mathcal{C} is a family of subsets of V , called convex sets , that satisfies: a) \emptyset,V\in\mathcal{C} ; b) For all \mathcal{C^{\prime}}\subseteq\mathcal{C} , we have \bigcap\mathcal{C^{\prime}}\in\mathcal{C} ; c) Every nested union of convex sets is a convex set. In the case of a finite set V , the condition of nested unions is always satisfied, and we can only consider the first two. We often say that the family \mathcal{C} is a convexity over V . For any S\subseteq V , the convex hull of S is the inclusion-wise minimum convex set C\in\mathcal{C} such that S\subseteq C . For a convex set C\in\mathcal{C} , an element p\in C is an extreme of C if p does not belong to the convex hull of C\setminus\{p\} . For a positive integer d , it is well-known that a convex set in \mathbb{R}^{d} is any subset S\subseteq\mathcal{R}^{d} such that, for any two points p_{1},p_{2}\in S , the points in the straight-line segment linking p_{1} to p_{2} must also belong to S . In this context, a well-known result is that any convex set in \mathbb{R}^{d} that is closed and bounded corresponds to the convex hull of its extreme points [ KreinMilman1940 , Minkowski1911 ] . More generally, a convexity \mathcal{C} defined over V is a convex geometry (a.k.a. geometric convexity ) if any convex set C\in\mathcal{C} is the convex hull of its extreme elements. When it is not necessarily the case, given a convex set C , we say that C is geometric if C is the convex hull of its extreme elements. When the set V is the set of vertices of a (directed) graph, the convexity space (V,\mathcal{C}) is a graph convexity . There are several graph convexities defined in the literature [ ADPS2025 ] . The study of graph convexities has received a lot of attention from the community, especially in the last 25 years. Most of them study (non-directed) graphs, even if some of the older works in this domain address the oriented case [ erdHos1972some , pfaltz1971convexity ] . Most graph convexities are defined in terms of (directed) paths of the input (resp. directed) graph. More precisely, the convex sets C in the family \mathcal{C} satisfy the following property: if u,w\in C , then all internal vertices of (resp. directed) (u,w) -paths satisfying some constraint \Pi must also belong to C . When the constraint \Pi is that the path is a shortest path, then the graph convexity is called geodesic . If \Pi corresponds to the property of being an induced path, then the convexity is called monophonic . When \Pi requires that the path has length two, we have the \opthree - convexity , while if the path is further required to be an induced/shortest path on three vertices, then such convexity is known as \opthrees - convexity . Note that, by definition, for any u,w\in C , one must consider all directed (u,w) -paths and all directed (w,u) -paths satisfying the constraint \Pi , which of course, may not necessarily contain the same internal vertices in the directed case. Graph convexities defined over directed graphs in the literature usually assume that they are indeed oriented graphs, which is a hypothesis that we also consider in this work. Recall that D is an oriented graph if it is an orientation of a simple graph G , i.e. D is obtained from G by replacing each edge of G by exactly one arc with the same endpoints. Consequently, D is a directed graph without loops, nor parallel, or symmetric arcs. Although graph convexity has been more extensively studied than digraph convexity, there is a substantial body of literature dedicated to \opthree -convexity [ AMM+2026 , erdHos1972some , PWW.08 ] . In a recent work [ AMM+2026 ] , the authors define the \opthrees -convexity in an oriented graph D in such a way that S is a convex set if for every u,w\in S , we have that any vertex v

Read the complete text