Adjacency labeling schemes and small classes of graphs

25^th February 2025, 13:00 Ashton Lecture Theatre
Julien Duron
ENS Lyon

Abstract

If 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.

The 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.