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. Same pattern: 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 make it concrete: Proposition 11 says global flow on a failure network G\A lives in H⁰_Z(X; F). Checking whether flows survive node removal is a cohomological computation — same question as "does removing B break A→C?"

One pattern, three triggers

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

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 →