Implicit Representations of Graphs and Randomized Communication

An implicit or local representation of a graph G=(V,E) is an assignment s: V -> {0,1}^* of labels to the vertices such that adjacency between any two vertices x and y can be decided only from the corresponding labels s(x) and s(y). 

A fundamental question is which hereditary graph classes admit implicit representations with labels of order optimal size. In particular, until recently one of the central questions in the area was the Implicit Graph Conjecture (IGC) positing that any factorial hereditary class (i.e., a class in which the number of n-vertex labeled graphs grows as a factorial-type function) admits an implicit representation with labels of size O(log(n)). 

In this talk we will present a connection between implicit representations of graphs and randomized communication problems that was developed to make progress towards the IGC and led to the refutation of the conjecture by Hatami and Hatami.

This is a joint work with Nathan Harms and Sebastian Wild.