Counterexamples
Lax330177.Examples · concepts/Lax330177/Examples.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A single repeated edge admits a simultaneous return walk under properness. A chain in reverse chronological order witnesses failure of transitivity.
- A simple graph can separate the traversal modes. The directed chain with both arcs available only at time 0 is simple and fails properness. Its first vertex reaches its last nonstrictly but cannot reach it strictly.
- Properness does not imply simplicity. One undirected edge appearing twice gives a proper graph that fails simplicity. The two opposite directed arcs are proper as well, since every two-step traversal returns to its starting vertex.
- A proper graph can have a walk with equal departure times. On a proper undirected graph, a nonstrict walk can traverse one edge and immediately traverse it back at the same time.
- Reachability can fail transitivity. In both traversal modes, the same three-vertex chain has 0 reaching 1 and 1 reaching 2, although 0 cannot reach 2.
- Reachability can be asymmetric even on a happy graph. The undirected chain with edge 1–2 at time 0 and edge 0–1 at time 1 is simple and proper. In both modes, 2 reaches 0 while 0 cannot reach 2.
- A temporal-edge trail can repeat a static edge. Crossing one undirected edge at time 0 and returning at time 1 gives a temporal-edge trail that repeats its static edge.
Concept map
Lean source view on GitHub
| 1 | import Mathlib |
| 2 | import Lax330177.Representations |
| 3 | import Lax330177.Settings |
| 4 | import Lax330177.Paths |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Counterexamples |
| 9 | type: definition |
| 10 | --- |
| 11 | A single repeated edge admits a simultaneous return walk under properness. A chain in reverse chronological order witnesses failure of transitivity. |
| 12 | |
| 13 | - [A simple graph can separate the traversal modes.](Lax330177Proofs.Basic.simple_separation.html) The directed chain with both arcs available only at time 0 is simple and fails properness. Its first vertex reaches its last nonstrictly but cannot reach it strictly. |
| 14 | - [Properness does not imply simplicity.](Lax330177Proofs.Basic.proper_separation.html) One undirected edge appearing twice gives a proper graph that fails simplicity. The two opposite directed arcs are proper as well, since every two-step traversal returns to its starting vertex. |
| 15 | - [A proper graph can have a walk with equal departure times.](Lax330177Proofs.Basic.bounce_same_time.html) On a proper undirected graph, a nonstrict walk can traverse one edge and immediately traverse it back at the same time. |
| 16 | - [Reachability can fail transitivity.](Lax330177Proofs.Basic.chain_failure.html) In both traversal modes, the same three-vertex chain has 0 reaching 1 and 1 reaching 2, although 0 cannot reach 2. |
| 17 | - [Reachability can be asymmetric even on a happy graph.](Lax330177Proofs.Basic.happy_asymmetry.html) The undirected chain with edge 1–2 at time 0 and edge 0–1 at time 1 is simple and proper. In both modes, 2 reaches 0 while 0 cannot reach 2. |
| 18 | - [A temporal-edge trail can repeat a static edge.](Lax330177.TrailSeparation.html) Crossing one undirected edge at time 0 and returning at time 1 gives a temporal-edge trail that repeats its static edge. |
| 19 | -/ |
| 20 | namespace Lax330177.Examples |
| 21 | open Lax330177.Representations |
| 22 | open Lax330177.Settings |
| 23 | open Lax330177.Paths |
| 24 | noncomputable section |
| 25 | attribute [local instance] Classical.propDecidable |
| 26 | abbrev repeatedEdge : Graph 2 where |
| 27 | lifetime := 2 |
| 28 | edge _ u v := u ≠ v |
| 29 | loopless := by intro _ _ h; exact h rfl |
| 30 | |
| 31 | def bounce : Walk repeatedEdge .strict 2 where |
| 32 | vertex := ![0, 1, 0] |
| 33 | time := id |
| 34 | available := by intro i; fin_cases i <;> decide |
| 35 | ordered := by intro i j h; exact h |
| 36 | |
| 37 | |
| 38 | |
| 39 | |
| 40 | def simultaneousBounce : Walk repeatedEdge .nonstrict 2 where |
| 41 | vertex := ![0, 1, 0] |
| 42 | time _ := (0 : Fin 2) |
| 43 | available := by intro i; fin_cases i <;> decide |
| 44 | ordered := by intro i j _; exact le_refl _ |
| 45 | |
| 46 | |
| 47 | abbrev backwardsChain : Graph 3 where |
| 48 | lifetime := 2 |
| 49 | edge t u v := |
| 50 | (t = 1 ∧ ((u = 0 ∧ v = 1) ∨ (u = 1 ∧ v = 0))) ∨ |
| 51 | (t = 0 ∧ ((u = 1 ∧ v = 2) ∨ (u = 2 ∧ v = 1))) |
| 52 | loopless := by intro t u; fin_cases t <;> fin_cases u <;> decide |
| 53 | |
| 54 | def firstLeg : Walk backwardsChain .strict 1 where |
| 55 | vertex := ![0, 1] |
| 56 | time _ := (1 : Fin 2) |
| 57 | available := by intro i; fin_cases i; decide |
| 58 | ordered := by intro i j h; have := i.isLt; have := j.isLt; change i.val < j.val at h; omega |
| 59 | |
| 60 | def secondLeg : Walk backwardsChain .strict 1 where |
| 61 | vertex := ![1, 2] |
| 62 | time _ := (0 : Fin 2) |
| 63 | available := by intro i; fin_cases i; decide |
| 64 | ordered := by intro i j h; have := i.isLt; have := j.isLt; change i.val < j.val at h; omega |
| 65 | |
| 66 | |
| 67 | |
| 68 | |
| 69 | |
| 70 | |
| 71 | |
| 72 | abbrev simultaneousChain : Graph 3 where |
| 73 | lifetime := 1 |
| 74 | edge _ u v := (u = 0 ∧ v = 1) ∨ (u = 1 ∧ v = 2) |
| 75 | loopless := by intro t u; fin_cases u <;> decide |
| 76 | |
| 77 | def chainPath : Walk simultaneousChain .nonstrict 2 where |
| 78 | vertex := id |
| 79 | time _ := 0 |
| 80 | available := by intro i; fin_cases i <;> decide |
| 81 | ordered := by intro i j h; exact le_rfl |
| 82 | |
| 83 | |
| 84 | |
| 85 | def reverseChainPath : Walk backwardsChain .strict 2 where |
| 86 | vertex := ![2,1,0] |
| 87 | time := id |
| 88 | available := by intro i; fin_cases i <;> decide |
| 89 | ordered := by intro i j h; exact h |
| 90 | |
| 91 | |
| 92 | end |
| 93 | end Lax330177.Examples |
| 94 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments