A phase transition in Erdős-Barak random graphs

2025/12/05 by Blanchard, Gilles, Curien, Nicolas, Krause, Klara +1
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2512.05756

Abstract

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

Citations

• A random walk among random graphs
• Increasing paths in random temporal graphs
• Determining a Points Configuration from a Subset of the Pairwise Distances
• Sharp Thresholds in Random Simple Temporal Graphs
• Long monotone trails in random edge-labelings of random graphs

Related

• The phase transition in random graphs - a simple proof
• Phase transitions for Erdos-Renyi graphs
• Phase transition in inhomogenous Erdős-Rényi random graphs via tree counting
• A combinatorial approach to phase transitions in random graph isomorphism problems
• Phase transition for the vacant set left by random walk on the giant component of a random graph