The Rosetta Stone

Chapter 6 · 35 term-pairs from the 2n-3 conjecture

One question, three languages

The temporal spanner conjecture asks: does every temporal clique K_n have a spanner with at most 2n-3 edges? This question is open.

The same question in codec language: does every video sequence have a compressed representation with at most 2n-3 reference edges that preserves full decodability? The codec community would call this the minimum GOP budget — how few I-frame and P-frame references suffice to reconstruct every frame? Open.

The same question in sheaf language: does every directed dependency graph with tropical stalks have a sub-complex of size 2n-3 that preserves exactness of the reachability sheaf? This would be a tropical sparsification theorem — a bound on the minimum support of a section that witnesses global connectivity. Open.

Three communities, three formulations, zero shared vocabulary. The first five chapters identified a handful of term-pairs at the theoretical level. Working the conjecture computationally — 25,000+ random matrices, exhaustive search through k=15, four Lean proofs — surfaced twenty-five more. The table below is the Rosetta Stone: every correspondence that survived adversarial testing.

Grading rubric

Genuine — same formal primitive or theorem pattern under relabeling. You can prove a statement in one field by translating a proof from the other.
Moderate — same structural role but different state space or objective. The analogy guides intuition but doesn't transfer proofs.
Structural — same problem shape. Useful for hypothesis generation, not for proof transfer.

Genuine parallels

Moderate parallels

Structural analogies

Reading the crosswalk

Chapters 1-5 identified a handful of term-pairs at the theoretical level. Working the conjecture computationally surfaced twenty-five more, mostly moderate or structural: correspondences that guide intuition but don't transfer proofs.

The strongest new cluster is #11-14: twist permutation ↔ motion field. σ = m⁺∘m⁻ captures temporal reference flow through the biclique — where does a column's earliest arrival send its latest departure? Fixed points are valid hubs (100% at k=7). Cycle structure determines how many hubs are needed. Derangements (no fixed points) mark the hard case. Each property has a codec counterpart: static regions, motion segmentation, full-motion scenes.

For the conjecture, #20 matters most: the O(n log n) → O(n) gap is the cost of hub ignorance. The dismountability algorithm recurses without knowing which half contains the valid hub. Each uninformed split adds edges. Recursion depth is log n. Codec engineers pay the same tax with adaptive GOP sizing — you don't know where the scene changes are until you've encoded past them.

The backward-pass architecture (#21, #33) suggests the resolution: don't search for the hub during the forward pass. Commit greedily, then repair in batch. Two passes suffice empirically. The gap between this empirical fact and a proof is where the conjecture lives.

The question that's open in all three fields

The same structural gap appears in each field:

The shared obstacle is the same in every formulation: the hub cannot be found locally. The temporal graph theorist can't identify the pivot vertex without reading the full matrix. The codec engineer can't place the I-frame without seeing the whole scene. The sheaf theorist can't locate the support of the witnessing section without computing the global reachability structure. The log factor in O(n log n) is the price all three pay for this ignorance.

The crosswalk doesn't solve the question. It makes visible that it's the same question, asked three times in three communities that don't share venues. A proof in any one field transfers to the other two via this table.

Proof tree (current state)

For readers working on the conjecture. The reduction from temporal cliques to extremally matched bicliques is complete (Carnevale et al. 2025). What remains is a single existence argument on the biclique.

PROVED (Lean, zero sorry):
  ConnectedPair.lean   — non-dismountable bicliques have a connected column pair
  PivotEdge.lean       — any M⁻ cross edge has |In∩Out| ≥ k+1 (full graph routing)
  NonDomination.lean   — M⁻ perm → no row dominates another; M⁺ → no col dominates
  Pigeonhole.lean      — no-injection lemma

PROVED (empirical, 25k+ matrices, exhaustive through k=15):
  Cross-only spanning  — cross edges alone span all pairs (A-A, B-B, A-B)
  2 hub pairs suffice  — M⁻ ∪ M⁺ ∪ star(h₁) ∪ star(c₁) ∪ star(h₂) ∪ star(c₂)
  Fixed-point hubs     — σ(c)=c → valid hub, 100% when fixed points exist (~60%)
  Edge monotonicity    — adding edges never breaks reachability (zero cascades)
  2 backward passes    — greedy forward + ≤2 hub stars, zero failures (870 samples)

THE GAP:
  Why do 2 hub pairs always suffice?
  Equivalently: why does every k×k all-distinct matrix admit a temporal
  spanner with ≤ 6k cross edges? (The 2n-3 constant is a separate question.)

  Obstacle: hub certification requires Θ(k²) matrix entries. No local
  criterion covers the derangement case (σ has no fixed points, ~40%).
  The log factor in O(n log n) is the cost of this ignorance.

DEAD ENDS (20+, see CLAUDE.md):
  Two-column routing, 3DM reduction, covering design, recursive O(n),
  Laman/rigidity, all local hub heuristics, NP-hardness via Set Cover,
  forward+backward trees, alteration method, greedy-latest-first, ...