extremal_tree_vertex_bound
def
For integers C, q ≥ 0, the extremal vertex bound F_C(q) is defined by 2^q - 1 if q ≤ C, and (2^C - 1) + 2^C * (q - C) if q > C.
Statement
def extremal_tree_vertex_bound (C q : ℕ) : ℕ- Defined in
- arXiv:2611.04184 Theorem 4.6 (Short permutation pattern waves: The complete length-five classification)
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Used by 1
- extremal_tree_vertex_bound_sharpFor any natural numbers C and q, there exists a binary tree t : BinaryTree ℕ such that (binary_tree_labels t).card ≤ q,…
Read back from the Lean
The function extremal_tree_vertex_bound, taking two natural numbers C and q, is defined as:
- 2 ^ q - 1 if q ≤ C;
- (2 ^ C - 1) + 2 ^ C * (q - C) otherwise (i.e., if q > C).
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
/-- The extremal vertex bound F_C(q) for binary trees with child-subtree overlap at most C and at most q classes. -/ def extremal_tree_vertex_bound (C q : ℕ) : ℕ := if q ≤ C then 2 ^ q - 1 else (2 ^ C - 1) + 2 ^ C * (q - C)