Graph and hypergraph limits

August 15 to August 19, 2011

at the

American Institute of Mathematics, Palo Alto, California

organized by

Oleg Pikhurko, Balazs Szegedy, and Jaroslav Nesetril

Original Announcement

This workshop will be devoted to the emerging theory of graph and hypergraph limits. The potential power and applicability of these concepts comes in the fact that for some definitions of convergence the corresponding limits have many different representations. For example, the limits of left-convergent sequences of graphs can be represented by 2-variable symmetric measurable functions, exchangeable distributions on infinite graphs, or reflection-positive graph parameters.

The aim of the workshop is both to develop the general theory of some natural notions of convergence (such as convergence of bounded-degree graphs, left-convergence of graphs and k-uniform hypergraphs) as well as to find ways of applying limits to concrete questions about finite structures, most notably to extremal (hyper)graph problems.

Some of the main open problems that the workshop will focus on are the following.

  1. The Aldous-Lyons Conjecture: For every graphing there is a sequence of bounded degree graphs convergent to it.
  2. Lovász' Conjecture: Every feasible finite system of linear inequalities in subgraph densities has a solution which is finitely forcible.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.