Small classes and Universal graphs
Time: 14:00 -- Location: bat 650, 445
summary: Given a set of graphs S, a graph U is said to be universal for S if every graph of S is an induced subgraph of U. In particular, the disjoint union of the graphs in S is universal for S. However in many cases there are much better choices for a universal graph: for instance, planar graphs on n vertices admit universal graphs of polynomial size.
In this talk, we study the relation between the size of S and the minimum size of universal graphs for S. Since the recent disproof of the Implicit Graph Conjecture by Hatami and Hatami, one of the most interesting cases has been that of small classes, namely hereditary classes of labeled graphs with at most n! c^n graphs on n vertices. These classes remain quite general, since they contain planar graphs, minor-closed classes, and even classes of bounded twin-width, while the class of cubic graphs is not small. In opposition to the more general factorial classes (with size (cn)!), we will show why sparse small classes admit universal graphs of polynomial size, and general small classes also admit ``relatively small'' universal graphs.
Translations: fr