Recent progress on implicit representations of graph classes

29^th November 2023, 14:00
John Sylvester

Abstract

An adjacency labeling scheme for a class of graphs C defines, for any n-vertex G in C, an assignment of labels to each vertex in G so that adjacency in G is determined by a (fixed) function of the two labels of the endpoints. By a counting argument, if there are |C_n| many n-vertex graphs in C then any adjacency labeling scheme needs labels with at least (log|C_n|)/n many bits. If such a scheme exists it is called an implicit representation. The existence of a labeling scheme with largest label f(n)-bits long is equivalent to the existence of a universal graph of size 2^f(n).


Many classes of graphs (e.g. minor-closed, bounded twin-width, bounded degeneracy) admit an implicit representation and in 1988 it was conjectured that all classes containing at most 2^{O(n\log n)} many n-vertex graphs (factorial classes) have an implicit representation (in this case of size O(log n )). Hatami & Hatami recently smashed this conjecture by using the probabilistic method to construct a factorial class requiring almost square root n size labels. I will sketch a proof of their amazing result along with some of our own results on questions of implicit representation for small and monotone classes.



Joint work with Édouard Bonnet, Julien Duron, Viktor Zamaraev & Maksim Zhukovskii