carpool_edge_crosses
def
An edge between vertices u and v in Fin n crosses a finite vertex subset S : Finset (Fin n) if either u ∈ S and v ∉ S, or v ∈ S and u ∉ S.
Statement
def carpool_edge_crosses {n : ℕ} (u v : Fin n) (S : Finset (Fin n)) : Prop
- Defined in
- arXiv:2611.00388 Section 2
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Used by 2
- carpool_witness_familyFix n, T, an edge sequence (u_t, v_t) and D >= 300. From the edges alone one builds a family W of pairs (t, S) with |W| <= 2 T…
- carpool_backward_step_slack_increaseFor natural numbers n and T, an integer D, trajectory d : ℕ → Fin n → ℤ, and receiver/sender functions a, b : ℕ → Fin n satisfying for all…
Read back from the Lean
Given a natural number n, two vertices u, v : Fin n, and a subset S : Finset (Fin n), carpool_edge_crosses u v S is defined to hold if and only if either u is in S and v is not in S, or v is in S and u is not in S (that is, exactly one of u or v belongs to S).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- An edge between u and v crosses subset S if exactly one endpoint belongs to S. -/ def carpool_edge_crosses {n : ℕ} (u v : Fin n) (S : Finset (Fin n)) : Prop := (u ∈ S ∧ v ∉ S) ∨ (v ∈ S ∧ u ∉ S)