When can transitivity emerge from cycle-suppressing dynamics?

DavidMartin
Messages
20
Reaction score
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:
  1. acyclic, and
  2. transitive,
thus forming a genuine partial order on V?

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.
 

Similar threads

  • · Replies 57 ·
2
Replies
57
Views
1K
  • · Replies 0 ·
Replies
0
Views
3K
  • · Replies 11 ·
Replies
11
Views
5K
  • · Replies 163 ·
6
Replies
163
Views
28K
  • · Replies 2 ·
Replies
2
Views
5K
Replies
1
Views
2K
  • · Replies 21 ·
Replies
21
Views
5K
  • · Replies 62 ·
3
Replies
62
Views
11K
  • · Replies 13 ·
Replies
13
Views
10K
  • · Replies 1 ·
Replies
1
Views
2K