Submit progress

on Erdős #1155 · graph theory

The statement

Construct a random graph on $n$ vertices in the following way: begin with the complete graph $K_n$ . At each stage, choose uniformly a random triangle in the graph and delete all the edges of this triangle. Repeat until the graph is triangle-free.

Describe the typical parameters and structure of such a graph. In particular, if $f(n)$ is the number of edges remaining, then is it true that

\mathbb{E}f(n)\asymp n^{3/2}

and that $f(n) \ll n^{3/2}$ almost surely?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.