Back to Search
Start Over
On paths, stars and wyes in trees
- Publication Year :
- 2016
-
Abstract
- 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.<br />Comment: 11 pages, 2 figures
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1601.01950
- Document Type :
- Working Paper