Tree Dimension and the Sauer-Shelah Dichotomy

2022/03/23 by Roland Walker, Walker, Roland
Computer Science · Mathematics · #03C45 #03C98 #05A05 #05C05 #68Q32 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Logic (math.LO) #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2203.12211

openalex publication_date 2022/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce tree dimension and its leveled variant in order to measure the complexity of leaf sets in binary trees. We then provide a tight upper bound on the size of such sets using leveled tree dimension. This, in turn, implies both the famous Sauer-Shelah Lemma for VC dimension and Bhaskar's version for Littlestone dimension, giving clearer insight into why these results place the exact same upper bound on their respective shatter functions. We also classify the isomorphism types of maximal leaf sets by tree dimension. Finally, we generalize this analysis to higher-arity trees.

Related

• Bounds for the higher topological complexity of configuration spaces of trees
• Leaf management
• Compaction for two models of logarithmic-depth trees: Analysis and Experiments
• Lower Bounds on the Size of General Branch-and-Bound Trees
• The lattice dimension of a tree