Combinatorics Seminar
Tom Bohman
Carnegie Mellon University
Random Triangle Removal
Abstract: We consider the following random process.
Start with the compete graph on $n$ vertices.
Choose a triangle $T$ uniformly at random from
the collection of all triangles in the graph
and remove the edges of $T$ from the graph.
Repeat this operation until the graph has no
more triangles.
Bollob\'as and Erd\H{o}s conjecture that with high
probability this process terminates at a
graph that has $\Theta( n^{3/2} ) $ edges.
In this talk we present the motivation for
this conjecture and outline an argument that
gives an approximate solution. Applications
of this result and directions for future work
will also be discussed.
Joint work with Alan Frieze and Eyal Lubetzky
Monday March 6, 2017 at 2:00 PM in SEO 612