IntervalFamily
An interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer intervals, where each vertex owns at most R intervals.
Statement
structure IntervalFamily (T : ColoredRootedTree) (R : ℕ)- Defined in
- arXiv:2611.03620 Definition 2.2
- 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,…
- instFintypeColoredRootedTreeThe vertex set of a colored rooted tree is finite.
- instDecEqColoredRootedTreeEquality on the vertices of a colored rooted tree is decidable.
- 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 8
- 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,…
- instFintypeIntervalFamilyThe collection of intervals in an interval family 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.
- 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
Given a colored rooted tree T and a natural number R, an IntervalFamily T R is a structure consisting of:
1. A type of indices ι, equipped with Fintype ι and DecidableEq ι.
2. A function interval : ι → Set ℤ assigning a set of integers to each index i : ι.
3. A proof interval_icc that for every index i : ι, there exist integers a, b : ℤ with a ≤ b such that interval i equals the closed interval Set.Icc a b (i.e., {x ∈ ℤ | a ≤ x ≤ b}).
4. A function owner : ι → T.V assigning each index to a vertex of T.
5. A proof owner_bound that for every vertex v : T.V, the number of indices i : ι such that owner i = v (the cardinality of the fiber of owner over v) is at most R.
6. A proof laminar that for every pair of indices i, j : ι, at least one of the three conditions holds:
- interval i ⊆ interval j,
- interval j ⊆ interval i, or
- interval i and interval j are disjoint (i.e., interval i ∩ interval j = ∅).
7. A function id : T.V → ℤ.
8. A proof id_inj that id is injective (∀ u v : T.V, id u = id v → u = v).
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 interval family for a colored tree with at most R intervals per vertex. -/ structure IntervalFamily (T : ColoredRootedTree) (R : ℕ) where ι : Type [fintype : Fintype ι] [decEq : DecidableEq ι] interval : ι → Set ℤ interval_icc : ∀ i : ι, ∃ a b : ℤ, a ≤ b ∧ interval i = Set.Icc a b owner : ι → T.V owner_bound : ∀ v : T.V, (Finset.univ.filter (fun i : ι => owner i = v)).card ≤ R laminar : ∀ i j : ι, interval i ⊆ interval j ∨ interval j ⊆ interval i ∨ Disjoint (interval i) (interval j) id : T.V → ℤ id_inj : Function.Injective id