See by year See by month Jump to month

Laszlo Szekely (University of South Carolina, Columbia): The number of induced subtrees in trees

 Download as iCal file
Monday, 4. July 2016, 14:30 - 15:30
Abstract. There is continuing interest in the distribution of small subgraphs of graphs by isomorphism type. For trees, the corresponding question is the distribution of small subtrees by isomorphism type, as a small random subset of vertices in a tree likely has no edges at all.
We prove the following conjecture of Bubeck and Linial: if in a sequence of trees, where the tree size goes to infinity, the proportion of $k$-vertex paths among $k$-vertex subtrees becomes negligible, then almost all $k$-vertex subtrees are stars. We also show that the maximum number of nonisomorphic subtrees (of all sizes) of trees on $n$ vertices is $O(5^{n/4})$.
Location : Bolyai Intézet, I. emelet, Riesz terem, Aradi Vértanúk tere 1., Szeged

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013