Co-sponsored by DIMACS and the Institute for Advanced Study
This workshop is devoted to two techniques which have wide application in theoretical discrete optimization: the semi-random method and Szemeredi's Regularity Lemma (by the semi-random method we mean the generation of combinatorial objects via repeated applications of the probabilistic method, e.g. the Rodl nibble or iterative applications of the Lovasz Local Lemma). The second of these techniques applies only to large graphs. Most applications of the first are to large structures. This explains the choice of these topics as the subject of a workshop held under the auspices of the Special Year on Large-Scale Discrete Optimization.
The Regularity Lemma states roughly that the vertices of any large enough graph can be split up into pieces so that the bipartite graph spanned by the edges between each pair of pieces behaves essentially like a random bipartite graph. Thus, it seems reasonable that the resultant structure is amenable to analysis via the semi-random method. The most ambitious goal of the workshop is to foster collaborative research projects which combine the Regularity Lemma and the semi-random method. However, the presentations given at the workshop will not be so narrowly focussed. There will be no contributed talks.
Limited funds are available to support participants.
Next: Call for Participation
Workshop Index
DIMACS Homepage