BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T123541Z
UID:Seminar-acto-1096@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20231129T140000
DTEND:20231129T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:John Sylvester : Recent progress on implicit representations of graph classes\n\nAn 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).\n\n\nMany 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.\n\n\n\nJoint work with Édouard Bonnet, Julien Duron, Viktor Zamaraev & Maksim Zhukovskii\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1096
LOCATION:
END:VEVENT
END:VCALENDAR