nearest_ancestor_of_color
def
Vertex u is the nearest proper ancestor of vertex v having color c if u is an ancestor of v with color c and no intermediate ancestor between u and v has color c.
Statement
def nearest_ancestor_of_color (T : ColoredRootedTree) (v : T.V) (c : Fin 4) (u : T.V) : Prop
- Defined in
- arXiv:2611.03620 Section 2
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Built on 2
- ColoredRootedTreeA finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices,…
- instPartialOrderColoredRootedTreeThe ancestorship relation on the vertices of a colored rooted tree forms a partial order.
- Used by 2
- contiguous_interval_family_depth_lower_boundFor all integers R ≥ 1 and d ≥ 0 there is a finite rooted tree, properly colored with the 4 colors 0..3, with at most 11(2R+1)^d vertices,…
- is_correct_interval_familyAn interval family is correct if for every vertex x and color c different from that of x, whenever x has a nearest proper ancestor u of…
Read back from the Lean
Given a colored rooted tree $T$, a vertex $v \in T.V$, a color $c \in \mathrm{Fin}\; 4$, and a vertex $u \in T.V$, the predicate nearest_ancestor_of_color T v c u holds if and only if:
1. $u < v$ (in the partial order on $T.V$),
2. the color of $u$ in $T$ is $c$ ($T.\mathrm{color}\; u = c$), and
3. for every vertex $w \in T.V$, if $u < w$ and $w < v$, then $T.\mathrm{color}\; w \neq c$.
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
/-- Nearest proper ancestor of color c. -/ def nearest_ancestor_of_color (T : ColoredRootedTree) (v : T.V) (c : Fin 4) (u : T.V) : Prop := u < v ∧ T.color u = c ∧ ∀ w : T.V, u < w → w < v → T.color w ≠ c