BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260916T134838Z
UID:Seminar-dept-1266@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250225T130000
DTEND:20250225T140000
SUMMARY:School Seminar Series
DESCRIPTION:Julien Duron: Adjacency labeling schemes and small classes of graphs\n\nIf one wants to map every city in the world, one could write an encyclopedia of all cities, with each page containing the graph of the roads of a particular city. The drawback of this approach is that the encyclopedia would need to be stored somewhere, and it could be extremely large. An Adjacency Labeling Scheme (ALS) aims to "compress" such a database by factoring out redundancies across different maps. The idea is to assign names to all places in all cities—possibly reusing names—such that if place "Newton" and place "Euler" are adjacent in one city, they are also adjacent in every other city containing them.\n\n\n\nThe goal of this talk is to investigate the relationship between the number of graphs we want to store and the number of distinct names required. A long-standing conjecture in the field was the Implicit Graph Conjecture, which claimed that for any hereditary—stable under vertex deletion—graph class that is not too large, an efficient ALS could always be found. However, its recent disproof by Hatami & Hatami highlights the wide behaviour of such graph classes. In this talk, we will focus on the case of small classes—specifically, hereditary classes of graphs with roughly n!2^n graphs on n vertices—and establish both lower and upper bounds on their possible ALS.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1266
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR