We consider the trajectories of points on under sequences of certain folding maps associated with reflections. The main result characterizes collections of folding maps that produce dense trajectories. The minimal number of maps in such a collection is d+1.
On an abstract level, our results are motivated by classical theorems about directed graphs, and more generally Markov chains on discrete state spaces. A graph is transitive if every vertex @math can be connected to every other vertex @math by a path of directed edges. Finding a minimal subset of edges that still connects all vertices is known to be a hard problem, particularly if the graph has cycles. As a practical alternative, Aho, Garey, and Ullmann developed the theory of transitive reductions, which are graphs on the same vertex set with the smallest possible number of edges @cite_10 . In our setting, the points @math play the role of vertices, and a pair @math with @math plays the role of a directed edge connecting @math to @math . Edge paths correspond to trajectories, and transitivity means that all trajectories are dense. Theorem gives necessary and sufficient conditions for transitivity, Proposition constructs a transitive reduction, and Proposition establishes the presence of cycles. The random walk defined in Eq. corresponds to the Markov chain defined by a weighted directed graph, with @math playing the role of the edge weights. Theorem and Corollary concern the steady-state of the Markov chain.
@cite_10
2110920860
We consider economical representations for the path information in a directed graph. A directed graph @math is said to be a transitive reduction of the directed graph G provided that (i) @math has a directed path from vertex u to vertex v if and only if G has a directed path from vertex u to vertex v, and (ii) there is no graph with fewer arcs than @math satisfying condition (i). Though directed graphs with cycles may have more than one such representation, we select a natural canonical representative as the transitive reduction for such graphs. It is shown that the time complexity of the best algorithm for finding the transitive reduction of a graph is the same as the time to compute the transitive closure of a graph or to perform Boolean matrix multiplication.