# 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.