interval_family_member_depth
The 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 contains the interval of I, I itself included.
Statement
noncomputable def interval_family_member_depth {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) (i : F.ι) : ℕ
- Defined in
- arXiv:2611.03620 (Adjacency Labeling Schemes of Size log n + O(log log* n) for Graphs of Bounded Treewidth), Definition 2.2 (depth of a member of F).
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 2
- IntervalFamilyAn interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer…
- ColoredRootedTreeA finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices,…
- Used by 3
- 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,…
- interval_family_member_depth_posEvery member of an interval family has depth at least 1, since it counts itself.
- 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 an implicit colored rooted tree T, an implicit natural number R, an interval family F over T with parameter R, and an element i : F.ι, interval_family_member_depth F i is defined as the cardinality (as a natural number, via Nat.card) of the subtype of elements j : F.ι such that both:
1. The owner vertex of j has the same color in T as the owner vertex of i (T.color (F.owner j) = T.color (F.owner i)), and
2. The interval associated with i is a subset of the interval associated with j (F.interval i ⊆ F.interval j).
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
noncomputable def interval_family_member_depth {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) (i : F.ι) : ℕ := Nat.card {j : F.ι // T.color (F.owner j) = T.color (F.owner i) ∧ F.interval i ⊆ F.interval j}