Autor:	Walker, Roland
Rok vydání:	2022
Předmět:	Mathematics - Combinatorics Mathematics - Logic 05C05 05A05 68Q32 03C45 03C98
Druh dokumentu:	Working Paper
Popis:	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. Comment: 9 pages, 3 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2203.12211 Zobrazit plný text záznamu View this record from Arxiv