Monday, June 17
Levering Hall Glass Pavilion
Asymptotics of Packing, Covering, and Coloring Problems
The "incremental random" method is an approach to combinatorial problems which "constructs" an object of some desired type (e.g. packing, covering, coloring...) in small random increments, or more precisely, in increments which are shown to exist by random means. In recent years this approach has been used to establish good asymptotics for a number of combinatorial problems_e.g. existence of a good matching in a hypergraph or a good coloring of the edges of a multigraph_for which traditional deterministic and random approaches provide much less satisfactory information.
In this talk we will try to give some idea of the workings of the method and of some of the problems to which it has been applied. We will also try to indicate connections with (i) the relation between a combinatorial (a.k.a. integer programming) problem and its fractional version (linear relaxation), and (ii) the hard-core probability distributions of statistical physics.
Jeffry N. Kahn