ColoredRootedTree
A finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices, linearly ordered ancestor sets, and adjacent nodes having different colors.
Statement
structure ColoredRootedTree- Defined in
- arXiv:2611.03620 Section 2.1
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 14
- instPartialOrderColoredRootedTreeThe ancestorship relation on the vertices of a colored rooted tree forms a partial order.
- nearest_ancestor_of_colorVertex 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…
- 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,…
- colored_tree_subtreeThe subtree rooted at vertex v consists of all descendants of v in the tree.
- instFintypeIntervalFamilyThe collection of intervals in an interval family is finite.
- instFintypeColoredRootedTreeThe vertex set of a colored rooted tree is finite.
- 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…
- interval_family_member_depthThe depth of a member I of an interval family: the number of members of the same color as I (the color of the owner) whose interval…
- interval_family_member_depth_posEvery member of an interval family has depth at least 1, since it counts itself.
- instDecEqIntervalFamilyEquality on intervals in an interval family is decidable.
- IntervalFamilyAn interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer…
- instDecEqColoredRootedTreeEquality on the vertices of a colored rooted tree is decidable.
- has_contiguous_subtreesAn interval family has contiguous subtrees if the identifier image of every subtree is a closed integer interval.
- interval_family_member_depth_le_cardThe depth of a member is at most the number of members of the family.
Read back from the Lean
The structure ColoredRootedTree defines a 4-colored finite rooted tree poset, consisting of:
- A type V of vertices;
- Typeclass instances [Fintype V], [DecidableEq V], and [PartialOrder V] providing finiteness, decidable equality, and a partial order ≤ on V;
- A designated vertex root : V;
- An axiom bot_le : ∀ v : V, root ≤ v, asserting that root is a least element of the poset;
- An axiom down_chain : ∀ u₁ u₂ v : V, u₁ ≤ v → u₂ ≤ v → u₁ ≤ u₂ ∨ u₂ ≤ u₁, asserting that the set of predecessors of any vertex v forms a chain (total order);
- A coloring function color : V → Fin 4;
- An axiom proper_coloring : ∀ u v : V, u < v → (∀ w : V, u ≤ w → w < v → w = u) → color u ≠ color v, asserting that if v covers u in the poset order (i.e., u < v with no element strictly between them, representing a directed edge from parent u to child v), then u and v receive distinct colors.
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
/-- A finite rooted tree properly 4-colored, structured as an ancestorship poset. -/ structure ColoredRootedTree where V : Type [fintype : Fintype V] [decEq : DecidableEq V] [partialOrder : PartialOrder V] root : V bot_le : ∀ v : V, root ≤ v down_chain : ∀ u₁ u₂ v : V, u₁ ≤ v → u₂ ≤ v → u₁ ≤ u₂ ∨ u₂ ≤ u₁ color : V → Fin 4 proper_coloring : ∀ u v : V, u < v → (∀ w : V, u ≤ w → w < v → w = u) → color u ≠ color v