Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 12.01.2017 at 12:20 in S6, there is the following noon lecture:

Paths vs. stars in the local profile of trees

Stephan Wagner

Abstract

For a given subtree size k, the local profile of a tree describes the distribution of the subtrees of size k in isomorphism classes. In this talk, we focus on paths and stars and provide an affirmative answer to a recent question by Bubeck and Linial. For a tree T, let p^(k)_1(T) be the proportion of paths among all k-vertex subtrees (induced connected subgraphs) of T, and let p^(k)_2(T) be the proportion of stars. Our main theorem states: if p^(k)_1(T_n)->0 for a sequence of trees T_1,T_2,... whose size tends to infinity, then p^(k)_2(T_n)->1. Both are also shown to be equivalent to the statement that the number of k-vertex subtrees grows superlinearly and the statement that the (k-1)-th degree moment grows superlinearly.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010