Joint LIDS and TOC Seminar: Structure, Randomness and Universality

Tuesday, October 31, 2017 - 4:00pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Noga Alon


Tel Aviv University and CMSA, Harvard University

Building and Room number

32-G449 (Kiva)


What is the minimum possible number of vertices of a graph that contains every k-vertex graph as an induced subgraph? What is the minimum possible number of edges in a graph that contains every k-vertex graph with maximum degree 3 as a subgraph? These questions and related one were initiated by Rado in the 60s, and received a considerable amount of attention over the years, partly motivated by algorithmic applications. The study of the subject combines probabilistic arguments and explicit, structured constructions. I will survey the topic focusing on a recent asymptotic solution of the first question, where an asymptotic formula, improving earlier estimates by several researchers, is obtained by combining combinatorial and probabilistic arguments with group theoretic tools.


Noga Alon is a Baumritter Professor of Mathematics and Computer Science in Tel Aviv University, Israel. He received his Ph. D. in Mathematics at the Hebrew University of Jerusalem in 1983 and had visiting positions in various research institutes including MIT, the Institute for Advanced Study in Princeton, IBM Almaden Research Center, Bell Laboratories, Bellcore and Microsoft Research. He joined Tel Aviv University in 1985, served as the head of the School of Mathematical Sciences in 1999-2000, and supervised about 20 PhD students. Since 2009 he is also a member of Microsoft Research, Israel. He serves on the editorial boards of more than a dozen international technical journals and has given invited lectures in many conferences, including plenary addresses in the 1996 European Congress of Mathematics and in the 2002 International Congress of Mathematician. He published more than five hundred research papers and one book.

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 and Combinatorial Number Theory.

He is an ACM Fellow and an AMS Fellow, a member of the Israel Academy of Sciences and Humanities since 1997 and of the Academia Europaea since 2008, and received the Erdös prize in 1989, the Feher prize in 1991, the Polya Prize in 2000, the Bruno Memorial Award in 2001, the Landau Prize in 2005, the Gödel Prize in 2005, the Israel Prize in 2008, the EMET Prize in 2011, the Dijkstra Prize in 2016, an Honorary Doctorate from ETH Zurich in 2013 and from the University of Waterloo in 2015.