A phase transition in Erdős-Barak random graphs

Abstract

We study monotone paths in Erdős-Rényi random graphs on numbered vertices. Benjamini & Tzalik established a phase transition at $p=\frac{\log n}{n}$ for this model. We refine the critical value to $p=\frac{\log n-\log \log n}{n}$ and identify the critical window of order $\hat{I}˜(1/n)$.

6 pages. We have added the acknowledgments (which may be worth reading for our French collegues)