binary_tree_bounded_child_overlap
For any type α with decidable equality and any natural number C, binary_tree_bounded_child_overlap C on BinaryTree α is defined recursively: it holds on nil, and on a node with left child l and right child r, it holds if and only if (binary_tree_labels l ∩ binary_tree_labels r).card ≤ C, and the property holds recursively on both l and r.
Statement
def binary_tree_bounded_child_overlap {α : Type*} [DecidableEq α] (C : ℕ) : BinaryTree α → Prop
- Defined in
- arXiv:2611.04184 Section 4.2 (Short permutation pattern waves: The complete length-five classification)
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 1
- binary_tree_labelsFor any type α with decidable equality, and any binary tree t : BinaryTree α, the finite set binary_tree_labels t : Finset α of labels…
- 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
Given a type α with decidable equality and a natural number C, binary_tree_bounded_child_overlap C is a predicate on binary trees t : BinaryTree α defined recursively:
- If t is nil, it is True.
- If t is a node with left subtree l and right subtree r (regardless of the node's label), it asserts that:
1. The cardinality of the intersection of the finite set of labels in l and the finite set of labels in r is at most C ((binary_tree_labels l ∩ binary_tree_labels r).card ≤ C),
2. binary_tree_bounded_child_overlap C l holds, and
3. binary_tree_bounded_child_overlap C r holds.
In other words, at every internal node in the tree, the number of distinct labels appearing in both the left subtree and the right subtree is at most 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
/-- Predicate stating that every vertex has left-right child subtree label overlap at most C. -/ def binary_tree_bounded_child_overlap {α : Type*} [DecidableEq α] (C : ℕ) : BinaryTree α → Prop | .nil => True | .node _ l r => (binary_tree_labels l ∩ binary_tree_labels r).card ≤ C ∧ binary_tree_bounded_child_overlap C l ∧ binary_tree_bounded_child_overlap C r