23 KAM Mathematical Colloquium

23 KAM Mathematical Colloquium

Prof. JOEL SPENCER

COURANT INSTITUTE, NEW YORK

ASYMPTOTIC PACKING

October 5, 1995
Lecture Room S6, Charles University, Malostranske nam. 25, Praha 1
10:30 AM

Abstract

Start with the complete graph on $n$ vertices and randomly pull out triangles (the vertices stay put, the edges are removed) until no triangles remain. How much, on average, remains. We have bounds, heuristics, computer evidence and conjectures, but no proofs. Approaches involve stochastic differential equations, Branching Processes, Martingales and a variety of other tools. More generally, given a family of objects (here triangles) each of a given size (here three) and we want to find (randomly or otherwise) a disjoint subfamily, a packing. Under quite general circumstances we can pack them to cover almost all (asymptotically) of the space (here the $n(n-1)/2$ edges). Getting a clear picture of how much space is {\em not} covered has proven more difficult.