Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Friday, November 18, 2016, 12:15 pm

**Duration**: 30 minutes

**Location**: CAB G11

**Speaker**: Jan Foniok (Manchester Metropolitan University)

Abstract: A hereditary graph class is a class of graphs closed under isomorphism and under taking induced subgraphs, and its speed is the number of graphs in it with vertex set {1, 2, ..., n} (as a function of n). It is known that the speed cannot be just any odd* function of n; for instance, if it is superpolynomial, then it is at least exponential. Some research has looked into the structure of graph classes with speed below or above a certain threshold. We study classes whose speed is at least equal to the Bell numbers; the n-th Bell number is defined as the number of partitions of the set {1, 2, ..., n} into subsets. (For example, the class of all graphs that are disjoint unions of cliques has exactly this speed.) Extending results of Balogh, Bollobás and Weinreich, we characterise all the minimal classes whose speed is at least the Bell number. As a consequence, we show that it is decidable whether a class described by a finite number of forbidden induced subgraphs has speed at least the Bell number. The complexity of this problem remains open. Finally, I hope to mention a link to the existence of infinitely many mutually non-isomorphic graphs in a hereditary class. Joint work with A. Atminas, A. Collins and V. Lozin. * Here, “odd” is not a mathematical term.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login