has_contiguous_subtrees
def
An interval family has contiguous subtrees if the identifier image of every subtree is a closed integer interval.
Statement
def has_contiguous_subtrees {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) : Prop
- Defined in
- arXiv:2611.03620 Proposition 3.3
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Built on 5
- ColoredRootedTreeA finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices,…
- IntervalFamilyAn interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer…
- colored_tree_subtreeThe subtree rooted at vertex v consists of all descendants of v in the tree.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- 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,…
Read back from the Lean
Given a colored rooted tree $T$, a natural number $R$, and an interval family $F$ associated with $T$ and $R$, has_contiguous_subtrees F asserts that for every vertex $v \in T.V$, there exist integers $a, b \in \mathbb{Z}$ such that the image under $F.\mathrm{id}$ of the subtree rooted at $v$ (i.e., the set of vertices $w \in T.V$ with $v \le w$) is equal to the closed integer interval $[a, b] = \{x \in \mathbb{Z} \mid a \le x \le b\}$.
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
/-- Contiguous subtree property: each subtree occupies consecutive integer positions. -/ def has_contiguous_subtrees {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) : Prop := ∀ v : T.V, ∃ a b : ℤ, F.id '' (colored_tree_subtree T v) = Set.Icc a b