Richard Karp, UCB, MSRI, and ICSI
Algorithmic probabilistic graph theory
This talk will demonstrate how the probabilistic analysis of algorithms can be used to study the existence of combinatorial objects with specified properties and to investigate the structure of random graphs and other random combinatorial objects. Our first example will be Joel Spencer's probabilistic proof of Turan's theorem, a basic theorem in extremal graph theory. Then, after an introduction to threshold phenomena in random graphs and random Boolean formulas, we will apply algorithmic analysis to study properties of sparse random graphs, such as the size of a maximum matching and the existence of a subgraph with a specified density. The mathematical tools will range from discrete probability to differential equations.