A variant of the Erdos-Renyi random graph process

2018/06/28 by Adam Logan, Mike Molloy, Logan, Adam +4
Computer Science · Mathematics · Physics and Astronomy · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Stochastic processes and statistical mechanics #math.CO

paper · pdf · doi:10.48550/arxiv.1806.10975

19 pages

arxiv created 2018/06/28 · openalex publication_date 2018/06/28 · arxiv updated 2018/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a natural variant of the Erdős-Rényi random graph process in which k vertices are special and are never put into the same connected component. The model is natural and interesting on its own, but is actually inspired by the combinatorial data fusion problem that itself is connected to a number of important problems in graph theory. We will show that a phase transition occurs when the number of special vertices is roughly n^1/3, where n is the number of vertices.

Related

• Explosive Percolation in Erdös-Rényi-Like Random Graph Processes
• A combinatorial approach to phase transitions in random graph isomorphism problems
• Phase transitions for Erdos-Renyi graphs
• A phase transition in Erdős-Barak random graphs
• Phase transition in inhomogenous Erdős-Rényi random graphs via tree counting