Chain Fragility

Chapter 2 · Casteigts et al. 2012, §4.4 · Krishnan 2014, Thm 5.12

Sequential dependency breaks. Same pattern in all three fields.

Three descriptions of the same break

A temporal graph journey breaks when timing fails to compose. A P-frame chain breaks when a reference is lost. A sheaf's local sections fail to extend globally when exactness fails. Different triggers, same structural pattern: downstream validity depends on every earlier link.

TVG: timing fails to compose

In a temporal graph, A→B at time t₁ and B→C at time t₂ only composes into a journey A→C if t₂ ≥ t₁ + ζ(e₁, t₁) — you must arrive at B before the next edge departs, including latency. When this fails, the journey breaks even though both edges exist.

Python

class TemporalGraph:
    """Minimal temporal graph: edges are (u, v, t) triples."""
    def __init__(self):
        self.edges = []

    def add_edge(self, u, v, t):
        self.edges.append((u, v, t))

    def journeys(self, start, end):
        """Find all time-respecting paths from start to end."""
        results = []
        self._dfs(start, end, -1, [start], results)
        return results

    def _dfs(self, current, end, last_time, path, results):
        if current == end:
            results.append(list(path))
            return
        for u, v, t in sorted(self.edges, key=lambda e: e[2]):
            if u == current and t >= last_time and v not in path:
                path.append(v)
                self._dfs(v, end, t, path, results)
                path.pop()

# Build a chain: A→B at t=1, B→C at t=2, C→D at t=3
g = TemporalGraph()
g.add_edge("A", "B", 1)
g.add_edge("B", "C", 2)
g.add_edge("C", "D", 3)

print("Intact chain:")
print(f"  A→D journeys: {g.journeys('A', 'D')}")
print(f"  A→C journeys: {g.journeys('A', 'C')}")

# Remove the B→C edge (timing failure / reference loss)
g.edges = [(u, v, t) for u, v, t in g.edges if not (u == "B" and v == "C")]

print("\nAfter removing B→C (t=2):")
print(f"  A→D journeys: {g.journeys('A', 'D')}")
print(f"  A→C journeys: {g.journeys('A', 'C')}")
print(f"  A→B journeys: {g.journeys('A', 'B')}")
print("\n→ Upstream survives. Downstream dies.")

class TemporalGraph:
    """Minimal temporal graph: edges are (u, v, t) triples."""
    def __init__(self):
        self.edges = []

def add_edge(self, u, v, t):
        self.edges.append((u, v, t))

def journeys(self, start, end):
        """Find all time-respecting paths from start to end."""
        results = []
        self._dfs(start, end, -1, [start], results)
        return results

def _dfs(self, current, end, last_time, path, results):
        if current == end:
            results.append(list(path))
            return
        for u, v, t in sorted(self.edges, key=lambda e: e[2]):
            if u == current and t >= last_time and v not in path:
                path.append(v)
                self._dfs(v, end, t, path, results)
                path.pop()

# Build a chain: A→B at t=1, B→C at t=2, C→D at t=3
g = TemporalGraph()
g.add_edge("A", "B", 1)
g.add_edge("B", "C", 2)
g.add_edge("C", "D", 3)

print("Intact chain:")
print(f"  A→D journeys: {g.journeys('A', 'D')}")
print(f"  A→C journeys: {g.journeys('A', 'C')}")

# Remove the B→C edge (timing failure / reference loss)
g.edges = [(u, v, t) for u, v, t in g.edges if not (u == "B" and v == "C")]

print("\nAfter removing B→C (t=2):")
print(f"  A→D journeys: {g.journeys('A', 'D')}")
print(f"  A→C journeys: {g.journeys('A', 'C')}")
print(f"  A→B journeys: {g.journeys('A', 'B')}")
print("\n→ Upstream survives. Downstream dies.")

Codecs: reference lost

A P-frame references a previous frame. If that reference is lost, the P-frame can't decode, and neither can anything depending on it. Break one link, sever the tail.

Python

class Frame:
    def __init__(self, name, frame_type, ref=None, data=None):
        self.name = name
        self.type = frame_type
        self.ref = ref
        self.data = data

def decode_sequence(frames):
    decoded = {}
    results = []
    for f in frames:
        if f.type == "I":
            decoded[f.name] = f.data
            results.append((f.name, "OK", f.data))
        elif f.type == "P":
            if f.ref in decoded:
                value = decoded[f.ref] + f.data
                decoded[f.name] = value
                results.append((f.name, "OK", value))
            else:
                results.append((f.name, "FAIL", "missing ref: " + f.ref))
    return results

# GOP: I₀ → P₁ → P₂ → P₃
frames = [
    Frame("I0", "I", data=100),
    Frame("P1", "P", ref="I0", data=5),
    Frame("P2", "P", ref="P1", data=3),
    Frame("P3", "P", ref="P2", data=7),
]

print("Intact GOP:")
for name, status, val in decode_sequence(frames):
    print(f"  {name}: {status} → {val}")

damaged = [f for f in frames if f.name != "P1"]

print("\nAfter losing P1:")
for name, status, val in decode_sequence(damaged):
    print(f"  {name}: {status} → {val}")
print("\n→ I0 survives. P2, P3 fail (missing chain link).")

class Frame:
    def __init__(self, name, frame_type, ref=None, data=None):
        self.name = name
        self.type = frame_type
        self.ref = ref
        self.data = data

def decode_sequence(frames):
    decoded = {}
    results = []
    for f in frames:
        if f.type == "I":
            decoded[f.name] = f.data
            results.append((f.name, "OK", f.data))
        elif f.type == "P":
            if f.ref in decoded:
                value = decoded[f.ref] + f.data
                decoded[f.name] = value
                results.append((f.name, "OK", value))
            else:
                results.append((f.name, "FAIL", "missing ref: " + f.ref))
    return results

# GOP: I₀ → P₁ → P₂ → P₃
frames = [
    Frame("I0", "I", data=100),
    Frame("P1", "P", ref="I0", data=5),
    Frame("P2", "P", ref="P1", data=3),
    Frame("P3", "P", ref="P2", data=7),
]

print("Intact GOP:")
for name, status, val in decode_sequence(frames):
    print(f"  {name}: {status} → {val}")

damaged = [f for f in frames if f.name != "P1"]

print("\nAfter losing P1:")
for name, status, val in decode_sequence(damaged):
    print(f"  {name}: {status} → {val}")
print("\n→ I0 survives. P2, P3 fail (missing chain link).")

Sheaves: exactness failure

Krishnan (2014, Theorem 5.12) proves that duality gaps — where max-flow is strictly less than min-cut — arise when directed sheaf cohomology fails to be exact. Local sections (valid flows on subnetworks) exist, but they don't compose into a global section. "Local consistency fails to globalize" is the algebraic form of chain fragility. (The three-way connection is this series' reading, not Krishnan's.)

Ghrist & Hiraoka ground this: Proposition 11 places global flow on a failure network G\A in H⁰_Z(X; F). Whether flows survive node removal becomes a cohomological computation: does removing B break A→C?

One pattern, three triggers

All three say the same thing: on a directed dependency graph, removing an intermediate node severs everything downstream that depends uniquely on it. The triggers differ (failed time composition, reference loss, exactness failure), but the dependency pattern is formally identical.

This is the one genuine parallel in the crosswalk. The others (next chapter) are forced.

Neighbors

Key references

Casteigts et al. 2012 — non-transitivity of temporal reachability (§4.4)
Krishnan 2014 — duality gaps as exactness failures (Thm 5.12)
Ghrist & Hiraoka — network robustness (Prop 11)

← The Operator Dictionary by june.kim What Each Field Has →