DIMACS Center, CoRE Building, Rutgers University

**Organizers:****László Lovász**, Microsoft Research and Eötvös Loránd University, lovasz@cs.elte.hu**Benny Sudakov**, Princeton University, bsudakov@math.princeton.edu

Many topics of research in mathematics, computer science and physics involve properties of very large graphs, or of graph sequences that grow asymptotically. For example, such topics arise in the study of Internet models, quasi-random graphs and other questions in graph theory, in property testing of large graphs, and in statistical mechanics. One of the areas of mathematics where these questions have been studied extensively is extremal graph theory. Given the central question in extremal graph theory concerning the existence of various small subgraphs, it might at first seem that this area has little to do with the other themes of this workshop, which are all probabilistic in nature. It turns out, however, that this is not the case. Indeed, one of the central results in this area is Szemerédi's Regularity Lemma, which has connections to, e.g., property testing and so-called quasi-random graphs. Quasi-random (also called pseudo-random) graphs were introduced by Thomason and Chung, Graham and Wilson. These graphs are deterministic, but are similar in many ways to random graphs: they have the same number of small subgraphs as a truly random graph, a partition into large subgraphs has similar cuts (number of edges between the different parts of the partitions), etc. In fact, these different characterizations have been proven to be equivalent.

Recently, a program has begun to generalize the results from quasi-random graphs to a large class of graph sequences . The work was originally motivated by an attempt to understand in which sense scale-free graphs like the Barabasi-Albert graph tend to a limit as their size goes to infinity, but turns out to have much wider scope. People working on this new program include researchers coming from many areas, including topology (Michael Freedman), group theory (Balazs Szegedy), combinatorics and computer science (Jeff Kahn, Laci Lovász, Lex Schrijver, Vera Sos, Katalin Vesztergombi) and probability theory and mathematical statistical physics (Christian Borgs, Jennifer Chayes).

One of the central notions in this program is the notion of a convergent
graph sequence *G _{n}*. For dense graphs, one of the many equivalent
definitions requires that for any finite graph

Other equivalent notions
involve uniform Szemerédi partitions, the number of graph homomorphisms
from *G _{n}* into weighted graphs

The workshop will bring together researchers from the fields of graph homomorphisms, extremal graph theory, quasi-random graphs, property testing, Internet modeling, probability theory and statistical physics (as practiced by mathematical physicists as well as theoretical physicists).

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on May 8, 2006.