While this submission is a draft, it cannot be used by other submissions.

Counterexamples

Lax330177.Examples · concepts/Lax330177/Examples.lean · lax-330177

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    A single repeated edge admits a simultaneous return walk under properness. A chain in reverse chronological order witnesses failure of transitivity.

    Concept map
    4 concepts; 6 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib
    2import Lax330177.Representations
    3import Lax330177.Settings
    4import Lax330177.Paths
    5
    6/-!
    7---
    8title: Counterexamples
    9type: definition
    10---
    11A 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-/
    20namespace Lax330177.Examples
    21open Lax330177.Representations
    22open Lax330177.Settings
    23open Lax330177.Paths
    24noncomputable section
    25attribute [local instance] Classical.propDecidable
    26abbrev repeatedEdge : Graph 2 where
    27 lifetime := 2
    28 edge _ u v := u ≠ v
    29 loopless := by intro _ _ h; exact h rfl
    30
    31def 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
    40def 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
    47abbrev 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
    54def 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
    60def 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
    72abbrev 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
    77def 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
    85def 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
    92end
    93end Lax330177.Examples
    94

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…