Abstract
We show that by restricting the degrees of the vertices of a graph to an arbitrary set \( \varDelta \), the threshold point \( \alpha (\varDelta ) \) of the phase transition for a random graph with \( n \) vertices and \( m = \alpha (\varDelta ) n \) edges can be either accelerated (e.g., \( \alpha (\varDelta ) \approx 0.381 \) for \( \varDelta = \{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}) = \tfrac{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 (\varDelta ) 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).
This work is partially supported by the French project MetACOnc, ANR-15-CE40-0014 and by the French project CNRS-PICS-22479.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bohman, T., Freize, A.: Avoiding a giant component. Random Struct. Algorithms 19(1), 75–85 (2001)
Bollobás, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Comb. 1, 311–316 (1980)
de Panafieu, É., Ramos, L.: Enumeration of graphs with degree constraints. In: Proceedings of the Meeting on Analytic Algorithmics and Combinatorics (2016)
Erdős, P., Rényi, A.: On the evolution of random graphs. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 5, 17–61 (1960)
Flajolet, P., Odlyzko, A.M.: The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25, 171–213 (1982)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge Press, Cambridge (2009)
Hatami, H., Molloy, M.: The scaling window for a random graph with a given degree sequence. Random Struct. Algorithms 41(1), 99–123 (2012)
Janson, S., Knuth, D.E., Łuczak, T., Pittel, B.: The birth of the giant component. Random Struct. Algorithms 4(3), 231–358 (1993)
Joos, F., Perarnau, G., Rautenbach, D., Reed, B.: How to determine if a random graph with a fixed degree sequence has a giant component. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 695–703 (2016)
Liebenau, A., Wormald, N.: Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph. arXiv preprint arXiv:1702.08373 (2017)
Molloy, M., Reed, B.A.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2/3), 161–180 (1995)
Nachmias, A., Peres, Y.: Critical random graphs: diameter and mixing time. Ann. Probab. 36(4), 1267–1286 (2008)
Noy, M., Ravelomanana, V., Rué, J.: On the probability of planarity of a random graph near the critical point. Proc. Am. Math. Soc. 143(3), 925–936 (2015)
Riordan, O.: The phase transition in the configuration model. Comb. Probab. Comput. 21(1–2), 265–299 (2012)
Riordan, O., Warnke, L.: Achlioptas process phase transitions are continuous. Ann. Appl. Probab. 22(4), 1450–1464 (2012)
Riordan, O., Warnke, L.: The phase transition in bounded-size Achlioptas processes. arXiv preprint arXiv:1704.08714 (2017)
Acknowledgements
We would like to thank Fedor Petrov for his help with a proof of technical condition for saddle-point analysis, Élie de Panafieu, Lutz Warnke, and several anonymous referees for their valuable remarks.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Dovgal, S., Ravelomanana, V. (2018). Shifting the Phase Transition Threshold for Random Graphs Using Degree Set Constraints. In: Bender, M., Farach-Colton, M., Mosteiro, M. (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science(), vol 10807. Springer, Cham. https://doi.org/10.1007/978-3-319-77404-6_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-77404-6_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-77403-9
Online ISBN: 978-3-319-77404-6
eBook Packages: Computer ScienceComputer Science (R0)