Workshop III: Topics in Graphs and Hypergraphs

November 2 - 6, 2009


Graph theory is one of the oldest branches of combinatorics, with history going back to the 18 century. This area and the closely related Theory of Hypergraphs experienced the most impressive growth in the last 50 years. During this time Extremal graph theory and Extremal set theory were developed extensively and extremal results found many applications in Computer Science, Information Theory, Number Theory and Geometry. One such result is Szemeredi’s regularity lemma, providing a deep structural theorem for large and dense graphs. In addition to numerous applications in combinatorics, this lemma and its recent generalization to hypergraphs, can be used, for example, to prove existence of arithmetic progressions in dense subsets of integers or to obtain algorithms for testing properties of graph. Closely related to the regularity lemma are the recent interesting research on graph limits, bridging between combinatorics and analysis. Other exciting lines of research include the development of the Structural Graph theory, and in particular the celebrated Graph Minor project.

The workshop will focus specifically on several major research directions in modern Graph and Hypergraph theory. These topics will include Ramsey theory, Extremal problems for graphs and hypergraphs and in particular Turan-type questions, Extremal set theory and its applications to Information theory, Computer science and Coding Theory, algebraic methods in extremal combinatorics, Szemeredi’s regularity Lemma for graphs and hypergraphs and its application to number theory and property testing, Graph sequences and limits of graphs, topological methods for graphs and hypergraphs, Spectral techniques in graph theory, expanders graphs and their applications, structural approach to graph theory, graph minors and application of graph theory to optimization.

Organizing Committee

Penny Haxell (University of Waterloo)
Dhruv Mubayi (University of Illinois at Chicago)
Vera Sos (Renyi Institute of Mathematics)
Benjamin Sudakov (University of California, Los Angeles (UCLA))
Jacques Verstraete (University of California, San Diego (UCSD))