Large-deviation properties of the largest 2-core component for random graphs
Institut für Physik, Carl von Ossietzky Universität Oldenburg, 26111 Oldenburg, Germany
a e-mail: email@example.com
Received: 22 November 2016
Revised: 16 December 2016
Published online: 5 April 2017
Distributions of the size of the largest component of the 2-core for Erdos-Rényi (ER) random graphs with finite connectivity c and a finite number N of nodes are studied. The distributions are obtained basically over the full range of the support, with probabilities down to values as small as 10−320. This is achieved by using an artificial finite-temperature (Boltzmann) ensemble. The distributions for the 2-core resemble roughly the results obtained previously for the largest components of the full ER random graphs, but they are shifted to much smaller probabilities (c ≤ 1) or to smaller sizes (c > 1). The numerical data is compatible with a convergence of the rate function to a limiting shape, i.e., the large-deviations principle apparently holds.
© EDP Sciences, Springer-Verlag, 2017