DavidMartin
- 20
- 3
- TL;DR
- Can cycle suppression in a directed graph cause transitivity to emerge, yielding a partial order without assuming transitivity from the start?
Let V be a finite set and let R⊆V×V be a directed binary relation.
Assume that R is not assumed to be transitive or acyclic a priori.
Equivalently, think of R as the edge set of a directed graph G=(V,E), possibly containing directed cycles.
I am interested in the following general question:
Suppose we define some structural or dynamical condition on R that penalizes or suppresses directed cycles (for example, by minimizing a functional that increases with the number or length of directed cycles).
Under what conditions can such a process lead to a relation that is:
In particular:
I am not asking about the transitive closure construction itself (which is well known), but rather about mechanisms or structural conditions under which transitivity can arise from a more general directed relation.
References to work in order theory, graph theory, or discrete dynamical systems would be appreciated.
Assume that R is not assumed to be transitive or acyclic a priori.
Equivalently, think of R as the edge set of a directed graph G=(V,E), possibly containing directed cycles.
I am interested in the following general question:
Suppose we define some structural or dynamical condition on R that penalizes or suppresses directed cycles (for example, by minimizing a functional that increases with the number or length of directed cycles).
Under what conditions can such a process lead to a relation that is:
- acyclic, and
- transitive,
In particular:
- Are there known results characterizing when cycle suppression forces a relation to converge (or reduce) to its transitive closure?
- Are there dynamical or variational frameworks on directed graphs where transitivity appears as a stable configuration rather than being imposed axiomatically?
- Is there a known characterization of when acyclicity plus some additional structural constraint implies transitivity?
I am not asking about the transitive closure construction itself (which is well known), but rather about mechanisms or structural conditions under which transitivity can arise from a more general directed relation.
References to work in order theory, graph theory, or discrete dynamical systems would be appreciated.