The Construction Gap

Chapter 7 · 10 paradigms, 46 variations, zero proofs

The construction

Pick a hub vertex. Connect it to all n-1 others (star). Connect the remaining n-1 vertices in a spanning tree (n-2 edges). Total: 2n-3. Check temporal reachability — if every pair can reach every other pair through time-respecting paths using only these edges, done.

For 99.8% of random temporal cliques (tested through n=20), some hub works with greedy tree selection. With exhaustive tree search, the true failure rate is 10× lower — 0.02% at K₆, vanishing by K₈. The "hub-less" instances always have a non-star spanner with ≤ 2n-4 edges.

Where the log factor was

The CPS fireworks algorithm proves O(n log n). The log factor comes from layered delegation: halving emitters each round, log(k) rounds, O(n) per round.

We tried to kill the log factor with sequential delegation — eliminate emitters one at a time instead of in batches. It doesn't work. The log factor is structural, not an analysis artifact: temporal filtering at each relay vertex consumes a constant fraction of the timestamp range. Root delegation gives Θ(k log k) edges at k=50. The CPS framework cannot yield O(n). A fundamentally different construction is needed.

The proof tree

spanner ≤ 2n-3
├── dismount (Carnevale et al. 2025) ✓
├── biclique characterization (Thm 3.10) ✓
├── connected pair exists ← Lean, zero sorry ✓
├── budget arithmetic ← proved (omega) ✓
├── M⁻ covers all A-A pairs ✓ NEW
├── M⁺ covers all B-B pairs ✓ NEW
└── biclique spanner ≤ 4k-3 ← OPEN
    ├── 46 proof strategies attempted, all dead
    ├── fixed-hop arguments: dead (journey lengths grow with k)
    ├── CPS delegation: Θ(k log k), log is structural
    └── the gap requires new mathematical tools

The gap is one lemma: show that every non-dismountable biclique with extremal matchings has a temporal spanner with ≤ 4k-3 cross edges. The M⁻/M⁺ matchings handle same-side pairs completely (proved). The remaining problem is cross-side routing within budget.

What doesn't work (10 paradigms)

The 46 variations cluster into 10 distinct proof paradigms. Calling them 46 separate hypotheses would be inflated — they're really variations on a smaller set of underlying ideas. Each paradigm died for a specific structural reason.

1. Hub-based constructions (~9 variations)

Star+tree, double-star, two-hub, star+early+late, K-early+late, inductive tree, three-case decomposition. All pick a hub vertex, add the star, then add "extra" edges. They work empirically but can't be proved because the extra-edge selection depends on global timestamp structure and resists analysis.

2. Fixed-hop relay analysis (~6 variations)

3-hop relays, 4-hop biclique routes, sequential delegation, median floor conjecture, LIVE/DZ framework, dead-zone analysis. All count relay edges assuming bounded journey length. Dead because the adversary forces journey lengths that grow with k (max hop = 4 at k=3, rising to 9 at k=6). No fixed-hop argument survives.

3. Tropical / semiring algebra (~6 variations)

Tropical rank, Develin-Sturmfels convexity, Praprotnik-Batagelj lifted ring, Lindström-Gessel-Viennot determinants, KKM lemma, monotone Dijkstra sweep. The (min,+) semiring lacks additive inverses. Rank-nullity fails. These methods compute the right object but can't bound it.

4. Probabilistic method (~4 variations)

Random tree selection, birthday bound on hubs, FKG / positive correlation, best-response Nash dynamics. All work for random timestamps but not adversarial ones. The concentration inequalities don't transfer to worst-case bounds.

5. Matroid / exchange (~3 variations)

Laman rigidity, exchange argument on minimal spanners, matroid exchange on matchings. Dead because minimal spanners can exceed 2n-3 (n=7: size 13 > 11). The problem is non-matroidal — locally irredundant ≠ globally optimal.

6. Set cover / covering design (~3 variations)

Covering hypergraph, VC dimension on rescue sets, X3C reduction. Dead because relay sets interact (submodular) rather than cover independently. Minimum set cover doesn't produce a valid spanner.

7. Dismountability reductions (~3 variations)

k-hop dismountability, recursive dismounting, Carnevale et al.'s "dismountability revisited." The reduction works (blocks ~99% of the problem) but explicit counterexamples exist: not all cliques are dismountable. The residual biclique needs a different proof.

8. Induction on size (~2 variations)

Recursive T(n) = T(n/2) + O(n), inductive extension from k×k to (k+1)×(k+1). Dead because the residual after vertex removal loses extremal matching structure, and the extension cost grows as O(k²) not O(1).

9. Local heuristics (~5 variations)

Per-vertex rules, column degree, timestamp spread, Farey mediants, forward ratio. All dead because an edge's relay value depends on global timestamp structure. No local metric predicts which edges are critical. Forward ratio is literally a tautology (always exactly 50%).

10. Distributed / game-theoretic (~1 variation)

Best-response dynamics converges in 2 rounds. Price of anarchy ≤ 1.25. Publishable as a distributed construction (the first one in the literature) but doesn't prove the 2n-3 bound.

What does work

M⁻ covers all A-A pairs. M⁺ covers all B-B pairs. (Proved.) In any extremally matched biclique, the column-minimum matching routes every same-side row pair through a 2-hop relay. The row-maximum matching does the same for column pairs. These I-frame edges are structurally complete for same-side reachability. The open problem is cross-side routing only.

Three-timestamp median. (Proved.) For any triangle {h,v,w} in K_n, edge {v,w} is "dead zone" for hub h iff its timestamp is the median of three. Average dead-zone degree = (n-2)/3. This identity is exact and gives the right framework for understanding spanner structure — but doesn't yield a bound.

Best-response dynamics converge in 2 rounds to a near-optimal spanner (Price of Anarchy ≤ 1.25). First distributed temporal spanner construction. Construction cost O(k&sup5;).

The negative mold

After probing 10 paradigms, the proof must:

• Handle unbounded journey lengths (fixed-hop arguments are dead)
• Reason about global temporal composition (local relay analysis fails)
• Work adversarially (probabilistic arguments over random timestamps don't transfer)
• Respect forward-but-not-backward transitivity
• Use tools that don't yet exist in the combinatorics literature

The most likely resolution: a new mathematical framework for adversarial temporal composition — perhaps tropical rank theory, temporal VC dimension, or sheaf-theoretic bounds. Each would be a thesis-scale contribution.

What we learned

The problem is genuinely hard. It has resisted three active research groups for seven years (CPS 2018, Angrick et al. 2024, Carnevale et al. 2025) and our probes at all ten paradigms. The gap is one lemma wide but that lemma requires mathematics that doesn't exist yet.

The construction is trivial. The proof isn't. The gap is waiting for new tools.

Full project: github.com/kimjune01/tvg — Lean proofs, Python experiments, 10 paradigms probed, research logs