Manuscript En05-A@1 · En05-A.tex · theorem · f076e703

Theorem: Cycle velocities and finite-time offset

Velocity sets and the discrete isotropy obstruction › Timed periodic dependency graphs · lines 1312–1351 · proof included or linked

En05-A@1#thm:polytope, En05-A@1#eq:finiteoffset

Back to manuscript

Let and . Every dependency path completed within time satisfies

The set of limiting path velocities as elapsed time tends to infinity is exactly . This is a statement about potential scheduled reachability, not transmission by every path.

Proof. Remove directed cycles from a finite walk until the remainder has no repeated vertex. Decompose the removed cycles into simple cycles. The remainder has at most edges, so its displacement has norm at most .

The cycle contribution is

Its total duration is no greater than . Since , the contribution belongs to , proving (eq:finiteoffset). Dividing by elapsed time proves the upper inclusion for limiting velocities.

Conversely, approximate a convex combination of cycle velocities and by spending the corresponding time proportions on repeated cycles and waiting. Strong connectivity supplies fixed connector walks between their base vertices. Choose repetition numbers tending to infinity; connector durations and displacements become negligible. Integer repetition numbers approximate the desired time proportions, giving every velocity in .

Displayed formulas in this passage

  • En05-A@1#eq:finiteoffset · line 1317

  • unlabeled · line 1336

Nearby in this section