simple_graph_tree_estimate
def
The tree estimate estim(T) = max{2, 1 + max_r (ρ_T(r) + leaf_T(r))}, where leaf_T(r) is the number of leaves of T other than r and ρ_T(r) = Σ deg(v)·2^{dist_T(r,v)} over the vertices v with v = r or deg(v) > 1.
Statement
noncomputable def simple_graph_tree_estimate {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] : ℕ
- Defined in
- arXiv:2610.09650 (The Almost Stacked Hypothesis: A Conjectural Analogue of Sjöstrand's Cover Pebbling Theorem), Definition 5.1 (the tree estimate). Defined for every finite graph; a leaf is a vertex of degree 1.
- Verified
- 12 Oct 2026
- Axioms
- none listed
- Used by 5
- path_graph_two_stacking_number_eq_tree_estimateConjecture 5.6 (OP-144) holds for the path on two vertices: stack(P₂) = estim(P₂) (both equal 3).
- star_graph_one_stacking_number_eq_tree_estimateConjecture 5.6 (OP-144) holds for the single-vertex tree K₁: stack(K₁) = estim(K₁) (both equal 2).
- path_graph_three_stacking_number_eq_tree_estimateConjecture 5.6 (OP-144) holds for the path on three vertices: stack(P₃) = estim(P₃) (both equal 7).
- star_graph_four_stacking_number_eq_tree_estimateConjecture 5.6 (OP-144) holds for the star K₁,₃ (center 0, leaves 1, 2, 3), the smallest tree that is not a path: stack(K₁,₃) =…
- two_le_simple_graph_tree_estimateThe tree estimate is at least 2.
Lean source view module on GitHub
/-- The tree estimate `estim(T) = max 2 (1 + max_r (ρ_T(r) + leaf_T(r)))`, with `ρ_T(r) = Σ deg v · 2^dist(r,v)` over `v = r` or `deg v > 1`, and `leaf_T(r)` the number of leaves other than `r`. -/ noncomputable def simple_graph_tree_estimate {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] : ℕ := max 2 (1 + Finset.univ.sup (fun r : V => (∑ v ∈ Finset.univ.filter (fun v => v = r ∨ 1 < T.degree v), T.degree v * 2 ^ T.dist r v) + (Finset.univ.filter (fun v => v ≠ r ∧ T.degree v = 1)).card))