# Combinatorics Seminar

When: Sunday, June 1, 10am

Where: Schreiber 309

Speaker: Uri Zwick, Tel Aviv U.

Title: Adjacency labeling schemes and induced-universal
graphs

## Abstract:

We describe a way of assigning LABELS to the vertices of any undirected
graph on up to n vertices, each composed of n/2+O(1) bits, such that
given the labels of two vertices, and no other information regarding
the graph, it is possible to decide whether or not the vertices are
adjacent in the graph. This is optimal, up to an additive constant, and
constitutes the first improvement in almost 50 years of an n/2+O(log n)
bound of Moon. As a consequence, we obtain an INDUCED-UNIVERSAL graph
for n-vertex graphs containing only O(2^{n/2}) vertices, which is optimal
up to a multiplicative constant, solving an open problem of Vizing from
1968. We obtain similar tight results for directed graphs, tournaments
and bipartite graphs.

Joint work with Stephen Alstrup, Haim Kaplan and Mikkel Thorup

redesigned by barak soreq