Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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

Duration: 30 minutes

Location: CAB G11

Speaker: Jan Foniok (Manchester Metropolitan University)

Hereditary graph classes, Bell numbers, and well quasi-ordering

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