Noon lecture

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

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

On Betti numbers of flag complexes with forbidden induced subgraphs (How many holes may a graph have)

Martin Tancer

Abstract

(based on a joint work with K. Adiprasito and E. Nevo)

We analyze the asymptotic extremal growth rate of the Betti numbers of clique complexes of graphs on n vertices not containing a fixed forbidden induced subgraph H. (The sum of the Betti number of a clique complex of graph may be considered as a possible criterion how to count the number of holes in a graph.)

In particular, we prove a theorem of the alternative: for any H the growth rate achieves exactly one of five possible exponentials. That is, the nth root of the maximal total Betti number over n-vertex graphs with no induced copy of H has a limit, as n tends to infinity, and, ranging over all H, exactly five different limits are attained. For the interesting case where H is the 4-cycle, the above limit is 1, and we prove a slightly superpolynomial upper bound.

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