2016/01/08 by Sébastien Bubeck, Bubeck, Sébastien, Katherine Edwards +5
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis #math.CO
paper · pdf · doi:10.48550/arxiv.1601.01950
11 pages, 2 figures
arxiv created 2016/01/08 · openalex publication_date 2016/01/08 · arxiv updated 2016/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We further the study of local profiles of trees. Bubeck and Linial showed that the set of 5-profiles contains a certain polytope, namely the convex hull of d-millipedes, and they proved that the segment [0-millipede, 1-millipede] corresponds to a face of the set of 5-profiles. Our main result shows that the segment [1-millipede, 2-millipede] also corresponds to a face. Surprisingly we also show that for d > 3 the segment [d-millipede, (d+1)-millipede] is not a face of the set of 5-profiles. We do so by exhibiting new trees which are generalized millipedes with intriguing patterns for their degree sequence. The plot thickens, and the set of 5-profiles remains a mysterious convex set.