Universal Graphs and Adjacency Labeling
A graph G is universal for a given finite family F of graphs if it contains every member of F as an induced subgraph. The existence of small universal graphs for F is equivalent to the existence of an economical way to label the vertices of any member of F in a way that enables one to check whether or not two vertices are adjacent by reading their labels. The study of this topic received a considerable amount of attention during the last decades. I will discuss it, focusing on the asymptotic solution of a problem of Moon and Vizing from the 60s regarding universal graphs for the family of all n-vertex graphs, and the investigation of universal graphs for
hereditary families with modest growth.
Noga Alon is a Professor of Mathematics at Princeton University and a Baumritter Professor Emeritus of Mathematics and Computer Science at Tel Aviv University, Israel.
His research interests are mainly in Combinatorics, Graph Theory and their applications in Theoretical Computer Science. His main contributions include the study of expander graphs and their applications, the investigation of derandomization techniques, the foundation of streaming algorithms, the development and applications of algebraic and probabilistic methods in Discrete Mathematics and the study of problems in Information Theory, Combinatorial Geometry, Combinatorial Number Theory and Computational Learning.
He is an ACM Fellow and an AMS Fellow, a member of the Israel Academy of Sciences and Humanities and of the Academia Europaea, and an honorary member of the Hungarian Academy of Sciences. He received the Erdös Prize, the Feher Prize, the Polya Prize, the Bruno Memorial Award, the Landau Prize, the Gödel Prize, the Israel Prize, the EMET Prize, the Dijkstra Prize, the Nerode Prize, the Paris Kanellakis Award, the Steele Prize for Mathematical Exposition, the Knuth Prize, the Shaw Prize in Mathematical Sciences and an Honorary Doctorate from ETH Zurich and from the University of Waterloo.