Shifting the Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints

Abstract

We show that by restricting the degrees of the vertices of a graph to an arbitrary set \( Δ\), the threshold point $\alpha (\Delta )$ of the phase transition for a random graph with $n$ vertices and $m=\alpha (\Delta )n$ edges can be either accelerated (e.g., $\alpha (\Delta )\approx 0.381$ for $\Delta =\{0,1,4,5\}$) or postponed (e.g., $\alpha (\{2^0,2^1,\cdots ,2^k,\cdots \})\approx 0.795$) compared to a classical Erdős--Rényi random graph with $\alpha ({\mathbb{Z}}_{\ge 0})=\frac{1}{2}$. In particular, we prove that the probability of graph being nonplanar and the probability of having a complex component, goes from $0$ to $1$ as $m$ passes $\alpha (\Delta )n$. We investigate these probabilities and also different graph statistics inside the critical window of transition (diameter, longest path and circumference of a complex component).

19 pages, coloured figures. Black-and-white printing is possible without essential lost of information in most pictures. Accepted to LATIN 2018

References in corpus (2)

• Achlioptas process phase transitions are continuous
• The phase transition in bounded-size Achlioptas processes