temporal_path_many_targets_one_frame_trap
For every k ≥ 2 there is a temporal graph on N = k² + k vertices, all of whose snapshots are spanning paths, together with k designated targets and a start vertex, such that every walk from that start visits at most one target by time N − 1. This is an obstruction to a prescribed-start one-frame coverage principle considered while working on OP-80; the asymptotic exploration bound remains open.
Statement
theorem temporal_path_many_targets_one_frame_trap (k : ℕ) (hk : 2 ≤ k) :
∃ (G : ℕ → SimpleGraph (Fin (k * k + k)))
(U : Finset (Fin (k * k + k))) (s : Fin (k * k + k)),
U.card = k ∧ (∀ t, is_spanning_path_graph (G t)) ∧
∀ w : ℕ → Fin (k * k + k), w 0 = s → is_temporal_walk G w →
∀ a < k * k + k, ∀ b < k * k + k,
w a ∈ U → w b ∈ U → w a = w b- Related work
- OP-80, arXiv:2610.06228 Sec. 7. A relocation construction developed in the deep session to test an auxiliary prescribed-start constant-fraction coverage principle. The construction is a diagnostic for that proof route and is not an asymptotic lower-bound advance.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_temporal_walkA temporal walk in a temporal graph (G_t)_t: at every time step t the agent either waits or traverses one edge of the snapshot G_t.
- is_spanning_path_graphA graph on n vertices is a spanning path if its vertices can be ordered so that exactly consecutive vertices are adjacent.
The proof, explained
The proof constructs a temporal graph on N = k² + k vertices where every snapshot is a spanning path defined by dynamically ordering the vertices. Initially, k targets occupy coordinates k², …, k² + k - 1 while grid vertices occupy coordinates 0, …, k² - 1. At time t = k² + j, target j swaps with grid vertex (j, 0), moving down to coordinate k * j. A walk starting at coordinate 0 cannot reach any target before its activation because the walker's coordinate at time t is at most t. Once target q is visited at time a ≥ k² + q, the remaining time before N is strictly less than k, which traps the walker within distance k of k * q where no further swaps occur, preventing it from reaching any other target.
At each time step, any vertex's coordinate increases to at most max(coordinate(t, v), t + 1).
Case analysis on whether v is a grid vertex (j, r) or a target j. If v = (j, r) with r = 0, its coordinate can only swap from k * j to k² + j when t + 1 ≥ k² + j, which is at most t + 1. If r ≠ 0, its coordinate is static. If v is a target j, its coordinate can only drop from k² + j to k * j < k² ≤ t + 1. In all cases, the coordinate at t + 1 is bounded by max(coordinate(t, v), t + 1).
uses
Nat.zero_add,le_trans,Nat.le_max_right,Nat.mul_lt_mul_of_pos_leftcoordinate (t + 1) v ≤ max (coordinate t v) (t + 1) := by rcases v with ⟨j, r⟩ | j · by_cases hr : r.val = 0 · simp only [coordinate, hr, true_and, Nat.zero_add] by_cases h0 : k * k + j.val ≤ t · have h1 : k * k + j.val ≤ t + 1 := by omega simp [h0, h1] · by_cases h1 : k * k + j.val ≤ t + 1 · simpa [h0, h1] using le_trans h1 (Nat.le_max_right (k * j.val) (t + 1)) · simp [h0, h1] · simp [coordinate, hr] · have hj : k * j.val < k * k := Nat.mul_lt_mul_of_pos_left j.isLt hk by_cases h0 : k * k + j.val ≤ t · have h1 : k * k + j.val ≤ t + 1 := by omega simp [coordinate, h0, h1] · by_cases h1 : k * k + j.val ≤ t + 1 · simp only [coordinate, h0, h1, if_true, if_false] exact le_trans (by omega) (Nat.le_max_right _ _) · simp [coordinate, h0, h1]
Coordinates below k * (q + 1) remain frozen after time k² + q.
Since t ≥ k² + q, any swap that occurs at time t + 1 corresponds to some index j with k² + j = t + 1 > k² + q, meaning j ≥ q + 1. The vertices swapped at time t + 1 have coordinates k * j ≥ k * (q + 1) and k² + j > k * (q + 1). Thus, any vertex with coordinate strictly less than k * (q + 1) is untouched by swaps at time t + 1 and keeps its coordinate.
uses
Nat.mul_le_mul_left,Nat.succ_le_of_lt,Nat.zero_addcoordinate (t + 1) v = coordinate t v := by have hq : k * (q.val + 1) ≤ k * k := Nat.mul_le_mul_left k (Nat.succ_le_of_lt q.isLt) rcases v with ⟨j, r⟩ | j · by_cases hr : r.val = 0 · simp only [coordinate, hr, true_and, Nat.zero_add] at hv ⊢ by_cases h0 : k * k + j.val ≤ t · have h1 : k * k + j.val ≤ t + 1 := by omega simp [h0, h1] · by_cases h1 : k * k + j.val ≤ t + 1 · have hj : q.val + 1 ≤ j.val := by omega have hmul := Nat.mul_le_mul_left k hj simp only [h0, if_false] at hv omega · simp [h0, h1] · simp [coordinate, hr] · by_cases h0 : k * k + j.val ≤ t · have h1 : k * k + j.val ≤ t + 1 := by omega simp [coordinate, h0, h1] · simp only [coordinate, h0, if_false] at hv omega
In any coordinate walk, the coordinate at time t changes by at most 1 in a single step.
By definition of a coordinate walk, the walker at time t either stays at the same vertex or moves to a vertex whose coordinate differs by ±1. In all cases, the coordinate difference is at most 1.
coordinate t (v t) ≤ coordinate t (v (t + 1)) + 1 := by rcases hv t with he | he | he · simp [he] · omega · omega
A coordinate walk starting at coordinate 0 satisfies coordinate(t, v(t)) ≤ t for all t.
By induction on t. The base case t = 0 holds because the initial coordinate is 0. In the induction step, the walk moves to v(t + 1) whose coordinate at time t is at most coordinate(t, v(t)) + 1 ≤ t + 1 by `coordinate_walk_bounds`. By `coordinate_step_bound`, coordinate(t + 1, v(t + 1)) ≤ max(coordinate(t, v(t + 1)), t + 1) ≤ t + 1.
uses
coordinate_walk_bounds,coordinate_step_bound∀ t, coordinate t (v t) ≤ t := by intro t induction t with | zero => omega | succ t ih => have hm := (coordinate_walk_bounds v hv t).1 have hs := coordinate_step_bound hk t (v (t + 1)) omega
Target q cannot be visited before its activation time k² + q.
Suppose v(a) = Sum.inr q. If a < k² + q, the target has not swapped yet, so its coordinate at time a is k² + q > a. But coordinate(a, v(a)) ≤ a by the global position bound, yielding a contradiction. Hence k² + q ≤ a.
(ha : v a = Sum.inr q) : k * k + q.val ≤ a := by have hp := hpos a rw [ha] at hp by_cases h : k * k + q.val ≤ a · exact h · simp [coordinate, h] at hp
Once target q is visited at time a, the walker remains within distance d of k * q at time a + d.
By induction on d. At d = 0, the target has swapped to coordinate k * q. For d + 1 < k, the walker's coordinate at time a + d is strictly less than k * (q + 1). By `coordinate_step_fixed`, the coordinate of v(a + d + 1) does not change between time a + d and a + d + 1. Combined with the one-step walk bound, the coordinate remains within distance d + 1 of k * q.
uses
coordinate_target_active,coordinate_walk_bounds,Nat.mul_add,Nat.mul_one,coordinate_step_fixedk * q.val ≤ coordinate (a + d) (v (a + d)) + d := by have hactive := coordinate_target_active v hpos a q ha intro d induction d with | zero => simp [ha, coordinate, hactive] | succ d ih => intro hd have hi := ih (by omega) have hm := coordinate_walk_bounds v hv (a + d) have hdlt : d + 1 < k := by omega have hp : coordinate (a + d) (v (a + d + 1)) < k * (q.val + 1) := by rw [Nat.mul_add, Nat.mul_one] omega have hfixed := coordinate_step_fixed hk q (a + d) (by omega) (v (a + d + 1)) hp have he : a + (d + 1) = a + d + 1 := by omega rw [he, hfixed] omega
Any two targets visited before time k² + k must be identical.
If targets q and r are visited at times a ≤ b < k² + k, the coordinate trapping property at d = b - a implies |k * r - k * q| ≤ b - a. Since a ≥ k² + q ≥ k² and b < k² + k, we have b - a < k. The only multiple of k strictly bounded by k in absolute value is 0, so k * q = k * r, which implies q = r.
uses
coordinate_after_target,coordinate_target_active,Fin.ext,lt_trichotomy,Nat.mul_le_mul_left,Nat.mul_add,Nat.mul_one(q r : Fin k) (ha : v a = Sum.inr q) (hbr : v b = Sum.inr r) : q = r := by have he : a + (b - a) = b := by omega have hh := coordinate_after_target hk v hv hpos a q ha (b - a) (by omega) rw [he, hbr] at hh have hractive := coordinate_target_active v hpos b r hbr simp only [coordinate, hractive, if_true] at hh have hd : b - a < k := by have := coordinate_target_active v hpos a q ha omega apply Fin.ext rcases lt_trichotomy q.val r.val with h | h | h · have hm : k * (q.val + 1) ≤ k * r.val := Nat.mul_le_mul_left k (by omega) rw [Nat.mul_add, Nat.mul_one] at hm omega · exact h · have hm : k * (r.val + 1) ≤ k * q.val := Nat.mul_le_mul_left k (by omega) rw [Nat.mul_add, Nat.mul_one] at hm omega
The coordinate swap operation swap_at is an involution on vertices.
Case analysis on the vertex: if v = (j, r) with r = 0, applying swap_at twice exchanges (j, 0) and Sum.inr j when k² + j ≤ t and restores them; if r ≠ 0 or k² + j > t, swap_at acts as the identity.
uses
Fin.extFunction.Involutive (swap_at hk t) := by intro v rcases v with ⟨j, r⟩ | j · by_cases hr : r.val = 0 · have he : r = (⟨0, hk⟩ : Fin k) := Fin.ext hr subst r by_cases h : k * k + j.val ≤ t <;> simp [swap_at, h] · simp [swap_at, hr] · by_cases h : k * k + j.val ≤ t <;> simp [swap_at, h]
The rank permutation value of a vertex at time t equals its coordinate at time t.
Unfolding rank_equiv into swap_at followed by index_equiv, the definition matches the coordinate function in every case.
(rank_equiv hk t v).val = coordinate t v := by change ((index_equiv k) (swap_at hk t v)).val = coordinate t v rcases v with ⟨j, r⟩ | j · by_cases h : r.val = 0 ∧ k * k + j.val ≤ t <;> simp [swap_at, coordinate, h] · by_cases h : k * k + j.val ≤ t <;> simp [swap_at, coordinate, h]
Every temporal walk on the graph sequence lifts to a coordinate walk.
At each step t, either the walk stays at the same vertex or moves along an edge of G(t). By definition of G(t) via pullback from pathGraph, adjacency means the rank coordinates differ by 1, which equals the coordinate difference at time t.
uses
congrArg,SimpleGraph.comap_adj,SimpleGraph.pathGraph_adj,Equiv.trans_apply,rank_coordinatecoordinate_walk (fun t => (index_equiv k).symm (w t)) := by intro t rcases hw t with he | he · left exact congrArg (index_equiv k).symm he · right simpa only [graph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj, order_fin, Equiv.trans_apply, rank_coordinate] using he
Construction of the temporal graph, target set U, and start vertex s, verifying U has size k and all snapshots are spanning paths.
The snapshot graphs G(t) are defined via order permutations, the target set U is the image of Fin k under the right injection into the vertex index, and s is the vertex (0, 0). Since the embedding is injective, |U| = k. Each snapshot graph is a spanning path by construction.
uses
Sum.inr.inj,Finset.card_image_of_injective,TemporalPathTargetTrap.graph_pathclassical have hkpos : 0 < k := by omega let z : Fin k := ⟨0, hkpos⟩ let f : Fin k → Fin (k * k + k) := fun j => (TemporalPathTargetTrap.index_equiv k) (Sum.inr j) let U : Finset (Fin (k * k + k)) := Finset.univ.image f let s := (TemporalPathTargetTrap.index_equiv k) (Sum.inl (z, z)) have hinj : Function.Injective f := by intro i j hij exact Sum.inr.inj ((TemporalPathTargetTrap.index_equiv k).injective hij) refine ⟨TemporalPathTargetTrap.graph hkpos, U, s, ?_, TemporalPathTargetTrap.graph_path hkpos, ?_⟩ · simp [U, Finset.card_image_of_injective _ hinj]
Any walk from s lifts to a coordinate walk starting at coordinate 0, bounded by t at time t.
Lifting w via index_equiv gives a coordinate walk v starting at coordinate 0. By `TemporalPathTargetTrap.coordinate_walk_position`, coordinate(t, v(t)) ≤ t for all t.
uses
TemporalPathTargetTrap.lifted_walk,Nat.mul_pos,TemporalPathTargetTrap.coordinate_walk_position· intro w hw0 hw let v : ℕ → TemporalPathTargetTrap.vertex k := fun t => (TemporalPathTargetTrap.index_equiv k).symm (w t) have hv : TemporalPathTargetTrap.coordinate_walk v := TemporalPathTargetTrap.lifted_walk hkpos w hw have hv0 : TemporalPathTargetTrap.coordinate 0 (v 0) = 0 := by have hsq : 0 < k * k := Nat.mul_pos hkpos hkpos simp [v, hw0, s, z, TemporalPathTargetTrap.coordinate, show ¬ k * k ≤ 0 by omega] have hpos := TemporalPathTargetTrap.coordinate_walk_position hkpos v hv hv0
Every temporal walk starting at s visits at most one target before time k² + k.
If the walk visits target q at time a and target r at time b with a, b < k² + k, we apply `coordinate_two_targets_equal` to deduce q = r. Hence the visited vertices w(a) and w(b) must be identical.
uses
Finset.mem_image.mp,Equiv.symm_apply_apply,le_total,TemporalPathTargetTrap.coordinate_two_targets_equal,congrArgintro a ha b hb haU hbU obtain ⟨q, -, hq⟩ := Finset.mem_image.mp haU obtain ⟨r, -, hr⟩ := Finset.mem_image.mp hbU have hqa : v a = Sum.inr q := by dsimp [v] rw [← hq] exact (TemporalPathTargetTrap.index_equiv k).symm_apply_apply _ have hrb : v b = Sum.inr r := by dsimp [v] rw [← hr] exact (TemporalPathTargetTrap.index_equiv k).symm_apply_apply _ have hqr : q = r := by rcases le_total a b with hab | hba · exact TemporalPathTargetTrap.coordinate_two_targets_equal hkpos v hv hpos a b hab hb q r hqa hrb · exact (TemporalPathTargetTrap.coordinate_two_targets_equal hkpos v hv hpos b a hba ha r q hrb hqa).symm exact hq.symm.trans ((congrArg f hqr).trans hr)
Nat.zero_add- 0 + n = n for any natural number n.
le_trans- Transitivity of the preorder: if a ≤ b and b ≤ c then a ≤ c.
Nat.le_max_right- For any natural numbers a and b, b ≤ max a b.
Nat.mul_lt_mul_of_pos_left- Multiplying both sides of a strict inequality by a strictly positive number preserves the strict inequality.
Nat.mul_le_mul_left- Multiplying both sides of an inequality by a natural number preserves the inequality.
Nat.succ_le_of_lt- If n < m, then n + 1 ≤ m.
Nat.mul_add- Multiplication distributes over addition on the right: n * (m + k) = n * m + n * k.
Nat.mul_one- Multiplying a natural number by one leaves it unchanged: n * 1 = n.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
lt_trichotomy- In a linear order, exactly one of a < b, a = b, or b < a holds.
congrArg- Applying a function to equal arguments yields equal results.
SimpleGraph.comap_adj- Two vertices are adjacent in a comap graph SimpleGraph.comap f G if and only if their images under f are adjacent in G.
SimpleGraph.pathGraph_adj- In the canonical path graph on Fin n, two vertices are adjacent if and only if their values differ by 1.
Equiv.trans_apply- Applying a composed equivalence (e₁ .trans e₂) is equivalent to applying e₁ and then e₂.
Sum.inr.inj- The right injection into a sum type is injective.
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the original set.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
Equiv.symm_apply_apply- Applying an equivalence after its inverse yields the identity.
le_total- In a linear order, any two elements satisfy a ≤ b or b ≤ a.
coordinate_walk_bounds- In a coordinate walk, the walker's coordinate at time t changes by at most 1 between step t and step t + 1.
coordinate_step_bound- The coordinate of any vertex at time t + 1 is bounded by the maximum of its coordinate at time t and t + 1.
coordinate_step_fixed- If t ≥ k² + q and the coordinate of v at time t is strictly less than k * (q + 1), then the coordinate of v does not change from t to t + 1.
coordinate_target_active- If a walk visits target q at time a, then k² + q ≤ a.
coordinate_after_target- After visiting target q at time a, the walker's coordinate remains within distance d of k * q at time a + d, provided a + d < k² + k.
TemporalPathTargetTrap.coordinate_two_targets_equal- If a walk visits target q at time a and target r at time b with a ≤ b < k² + k, then q = r.
rank_coordinate- The rank equivalence assigns each vertex its coordinate at time t.
TemporalPathTargetTrap.graph_path- Each snapshot graph G(t) is a spanning path graph.
TemporalPathTargetTrap.lifted_walk- Every temporal walk on the graph sequence lifts to a coordinate walk on the vertex set.
TemporalPathTargetTrap.coordinate_walk_position- A coordinate walk starting at coordinate 0 stays bounded by t at time t.
- The snapshot graphs G(t) are defined as pullbacks (comaps) of a standard path graph on Fin (k² + k) along dynamic order bijections, so Lean verifies the spanning path property directly from the construction.
- Several step-to-step inequalities on coordinates and indices are discharged by linear integer arithmetic (`omega`) following algebraic rewrites and case splits.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
namespace TemporalPathTargetTrapprivate abbrev vertex (k : ℕ) := (Fin k × Fin k) ⊕ Fin kprivate def coordinate {k : ℕ} (t : ℕ) : vertex k → ℕ | Sum.inl (j, r) => if r.val = 0 ∧ k * k + j.val ≤ t then k * k + j.val else r.val + k * j.val | Sum.inr j => if k * k + j.val ≤ t then k * j.val else k * k + j.valprivate theorem coordinate_step_bound {k : ℕ} (hk : 0 < k) (t : ℕ) (v : vertex k) : coordinate (t + 1) v ≤ max (coordinate t v) (t + 1) := by rcases v with ⟨j, r⟩ | j · by_cases hr : r.val = 0 · simp only [coordinate, hr, true_and, Nat.zero_add] by_cases h0 : k * k + j.val ≤ t · have h1 : k * k + j.val ≤ t + 1 := by omega simp [h0, h1] · by_cases h1 : k * k + j.val ≤ t + 1 · simpa [h0, h1] using le_trans h1 (Nat.le_max_right (k * j.val) (t + 1)) · simp [h0, h1] · simp [coordinate, hr] · have hj : k * j.val < k * k := Nat.mul_lt_mul_of_pos_left j.isLt hk by_cases h0 : k * k + j.val ≤ t · have h1 : k * k + j.val ≤ t + 1 := by omega simp [coordinate, h0, h1] · by_cases h1 : k * k + j.val ≤ t + 1 · simp only [coordinate, h0, h1, if_true, if_false] exact le_trans (by omega) (Nat.le_max_right _ _) · simp [coordinate, h0, h1]private theorem coordinate_step_fixed {k : ℕ} (hk : 0 < k) (q : Fin k) (t : ℕ) (ht : k * k + q.val ≤ t) (v : vertex k) (hv : coordinate t v < k * (q.val + 1)) : coordinate (t + 1) v = coordinate t v := by have hq : k * (q.val + 1) ≤ k * k := Nat.mul_le_mul_left k (Nat.succ_le_of_lt q.isLt) rcases v with ⟨j, r⟩ | j · by_cases hr : r.val = 0 · simp only [coordinate, hr, true_and, Nat.zero_add] at hv ⊢ by_cases h0 : k * k + j.val ≤ t · have h1 : k * k + j.val ≤ t + 1 := by omega simp [h0, h1] · by_cases h1 : k * k + j.val ≤ t + 1 · have hj : q.val + 1 ≤ j.val := by omega have hmul := Nat.mul_le_mul_left k hj simp only [h0, if_false] at hv omega · simp [h0, h1] · simp [coordinate, hr] · by_cases h0 : k * k + j.val ≤ t · have h1 : k * k + j.val ≤ t + 1 := by omega simp [coordinate, h0, h1] · simp only [coordinate, h0, if_false] at hv omegaprivate def coordinate_walk {k : ℕ} (v : ℕ → vertex k) : Prop := ∀ t, v (t + 1) = v t ∨ coordinate t (v t) + 1 = coordinate t (v (t + 1)) ∨ coordinate t (v (t + 1)) + 1 = coordinate t (v t)private theorem coordinate_walk_bounds {k : ℕ} (v : ℕ → vertex k) (hv : coordinate_walk v) (t : ℕ) : coordinate t (v (t + 1)) ≤ coordinate t (v t) + 1 ∧ coordinate t (v t) ≤ coordinate t (v (t + 1)) + 1 := by rcases hv t with he | he | he · simp [he] · omega · omegaprivate theorem coordinate_walk_position {k : ℕ} (hk : 0 < k) (v : ℕ → vertex k) (hv : coordinate_walk v) (hv0 : coordinate 0 (v 0) = 0) : ∀ t, coordinate t (v t) ≤ t := by intro t induction t with | zero => omega | succ t ih => have hm := (coordinate_walk_bounds v hv t).1 have hs := coordinate_step_bound hk t (v (t + 1)) omegaprivate theorem coordinate_target_active {k : ℕ} (v : ℕ → vertex k) (hpos : ∀ t, coordinate t (v t) ≤ t) (a : ℕ) (q : Fin k) (ha : v a = Sum.inr q) : k * k + q.val ≤ a := by have hp := hpos a rw [ha] at hp by_cases h : k * k + q.val ≤ a · exact h · simp [coordinate, h] at hpprivate theorem coordinate_after_target {k : ℕ} (hk : 0 < k) (v : ℕ → vertex k) (hv : coordinate_walk v) (hpos : ∀ t, coordinate t (v t) ≤ t) (a : ℕ) (q : Fin k) (ha : v a = Sum.inr q) : ∀ d, a + d < k * k + k → coordinate (a + d) (v (a + d)) ≤ k * q.val + d ∧ k * q.val ≤ coordinate (a + d) (v (a + d)) + d := by have hactive := coordinate_target_active v hpos a q ha intro d induction d with | zero => simp [ha, coordinate, hactive] | succ d ih => intro hd have hi := ih (by omega) have hm := coordinate_walk_bounds v hv (a + d) have hdlt : d + 1 < k := by omega have hp : coordinate (a + d) (v (a + d + 1)) < k * (q.val + 1) := by rw [Nat.mul_add, Nat.mul_one] omega have hfixed := coordinate_step_fixed hk q (a + d) (by omega) (v (a + d + 1)) hp have he : a + (d + 1) = a + d + 1 := by omega rw [he, hfixed] omegaprivate theorem coordinate_two_targets_equal {k : ℕ} (hk : 0 < k) (v : ℕ → vertex k) (hv : coordinate_walk v) (hpos : ∀ t, coordinate t (v t) ≤ t) (a b : ℕ) (hab : a ≤ b) (hb : b < k * k + k) (q r : Fin k) (ha : v a = Sum.inr q) (hbr : v b = Sum.inr r) : q = r := by have he : a + (b - a) = b := by omega have hh := coordinate_after_target hk v hv hpos a q ha (b - a) (by omega) rw [he, hbr] at hh have hractive := coordinate_target_active v hpos b r hbr simp only [coordinate, hractive, if_true] at hh have hd : b - a < k := by have := coordinate_target_active v hpos a q ha omega apply Fin.ext rcases lt_trichotomy q.val r.val with h | h | h · have hm : k * (q.val + 1) ≤ k * r.val := Nat.mul_le_mul_left k (by omega) rw [Nat.mul_add, Nat.mul_one] at hm omega · exact h · have hm : k * (r.val + 1) ≤ k * q.val := Nat.mul_le_mul_left k (by omega) rw [Nat.mul_add, Nat.mul_one] at hm omegaprivate def index_equiv (k : ℕ) : vertex k ≃ Fin (k * k + k) := (Equiv.sumCongr (finProdFinEquiv : Fin k × Fin k ≃ Fin (k * k)) (Equiv.refl (Fin k))).trans finSumFinEquiv@[simp] private theorem index_inl {k : ℕ} (j r : Fin k) : ((index_equiv k) (Sum.inl (j, r))).val = r.val + k * j.val := rfl@[simp] private theorem index_inr {k : ℕ} (j : Fin k) : ((index_equiv k) (Sum.inr j)).val = k * k + j.val := rflprivate def swap_at {k : ℕ} (hk : 0 < k) (t : ℕ) : vertex k → vertex k | Sum.inl (j, r) => if r.val = 0 ∧ k * k + j.val ≤ t then Sum.inr j else Sum.inl (j, r) | Sum.inr j => if k * k + j.val ≤ t then Sum.inl (j, ⟨0, hk⟩) else Sum.inr jprivate theorem swap_at_involutive {k : ℕ} (hk : 0 < k) (t : ℕ) : Function.Involutive (swap_at hk t) := by intro v rcases v with ⟨j, r⟩ | j · by_cases hr : r.val = 0 · have he : r = (⟨0, hk⟩ : Fin k) := Fin.ext hr subst r by_cases h : k * k + j.val ≤ t <;> simp [swap_at, h] · simp [swap_at, hr] · by_cases h : k * k + j.val ≤ t <;> simp [swap_at, h]private def swap_equiv {k : ℕ} (hk : 0 < k) (t : ℕ) : vertex k ≃ vertex k := ⟨swap_at hk t, swap_at hk t, swap_at_involutive hk t, swap_at_involutive hk t⟩private def rank_equiv {k : ℕ} (hk : 0 < k) (t : ℕ) : vertex k ≃ Fin (k * k + k) := (swap_equiv hk t).trans (index_equiv k)@[simp] private theorem rank_coordinate {k : ℕ} (hk : 0 < k) (t : ℕ) (v : vertex k) : (rank_equiv hk t v).val = coordinate t v := by change ((index_equiv k) (swap_at hk t v)).val = coordinate t v rcases v with ⟨j, r⟩ | j · by_cases h : r.val = 0 ∧ k * k + j.val ≤ t <;> simp [swap_at, coordinate, h] · by_cases h : k * k + j.val ≤ t <;> simp [swap_at, coordinate, h]private def order_fin {k : ℕ} (hk : 0 < k) (t : ℕ) : Equiv.Perm (Fin (k * k + k)) := (index_equiv k).symm.trans (rank_equiv hk t)private def graph {k : ℕ} (hk : 0 < k) (t : ℕ) : SimpleGraph (Fin (k * k + k)) := (SimpleGraph.pathGraph (k * k + k)).comap (order_fin hk t)private theorem graph_path {k : ℕ} (hk : 0 < k) (t : ℕ) : is_spanning_path_graph (graph hk t) := ⟨order_fin hk t, fun _ _ => SimpleGraph.pathGraph_adj⟩private theorem lifted_walk {k : ℕ} (hk : 0 < k) (w : ℕ → Fin (k * k + k)) (hw : is_temporal_walk (graph hk) w) : coordinate_walk (fun t => (index_equiv k).symm (w t)) := by intro t rcases hw t with he | he · left exact congrArg (index_equiv k).symm he · right simpa only [graph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj, order_fin, Equiv.trans_apply, rank_coordinate] using heend TemporalPathTargetTraptheorem temporal_path_many_targets_one_frame_trap (k : ℕ) (hk : 2 ≤ k) : ∃ (G : ℕ → SimpleGraph (Fin (k * k + k))) (U : Finset (Fin (k * k + k))) (s : Fin (k * k + k)), U.card = k ∧ (∀ t, is_spanning_path_graph (G t)) ∧ ∀ w : ℕ → Fin (k * k + k), w 0 = s → is_temporal_walk G w → ∀ a < k * k + k, ∀ b < k * k + k, w a ∈ U → w b ∈ U → w a = w b := by classical have hkpos : 0 < k := by omega let z : Fin k := ⟨0, hkpos⟩ let f : Fin k → Fin (k * k + k) := fun j => (TemporalPathTargetTrap.index_equiv k) (Sum.inr j) let U : Finset (Fin (k * k + k)) := Finset.univ.image f let s := (TemporalPathTargetTrap.index_equiv k) (Sum.inl (z, z)) have hinj : Function.Injective f := by intro i j hij exact Sum.inr.inj ((TemporalPathTargetTrap.index_equiv k).injective hij) refine ⟨TemporalPathTargetTrap.graph hkpos, U, s, ?_, TemporalPathTargetTrap.graph_path hkpos, ?_⟩ · simp [U, Finset.card_image_of_injective _ hinj] · intro w hw0 hw let v : ℕ → TemporalPathTargetTrap.vertex k := fun t => (TemporalPathTargetTrap.index_equiv k).symm (w t) have hv : TemporalPathTargetTrap.coordinate_walk v := TemporalPathTargetTrap.lifted_walk hkpos w hw have hv0 : TemporalPathTargetTrap.coordinate 0 (v 0) = 0 := by have hsq : 0 < k * k := Nat.mul_pos hkpos hkpos simp [v, hw0, s, z, TemporalPathTargetTrap.coordinate, show ¬ k * k ≤ 0 by omega] have hpos := TemporalPathTargetTrap.coordinate_walk_position hkpos v hv hv0 intro a ha b hb haU hbU obtain ⟨q, -, hq⟩ := Finset.mem_image.mp haU obtain ⟨r, -, hr⟩ := Finset.mem_image.mp hbU have hqa : v a = Sum.inr q := by dsimp [v] rw [← hq] exact (TemporalPathTargetTrap.index_equiv k).symm_apply_apply _ have hrb : v b = Sum.inr r := by dsimp [v] rw [← hr] exact (TemporalPathTargetTrap.index_equiv k).symm_apply_apply _ have hqr : q = r := by rcases le_total a b with hab | hba · exact TemporalPathTargetTrap.coordinate_two_targets_equal hkpos v hv hpos a b hab hb q r hqa hrb · exact (TemporalPathTargetTrap.coordinate_two_targets_equal hkpos v hv hpos b a hba ha r q hrb hqa).symm exact hq.symm.trans ((congrArg f hqr).trans hr)