k-core thresholds of the Erdős–Rényi random graph

edit · history · discussion · files · short url · statistical mechanics combinatorics probability theory

Numbers

$k$

$c_k$

3.350918871511672773156814404987098076190626590909356005328111228070177491045217990747563631554521917

comment: The minimum is attained at $\lambda_{3}=1.79328213290$, and the $3$-core, when it first appears, has about $0.267580654988\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{3})\geq 3)$ [1].

5.149402746986453309205780306874702219721431580445989663938902883996203674228102712799074136530994881

comment: The minimum is attained at $\lambda_{4}=3.38363428285$, and the $4$-core, when it first appears, has about $0.438061713058\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{4})\geq 4)$ [1].

6.799275488618085713554858948433881689611001560114832621433538808240774082265154295363651249651653632

comment: The minimum is attained at $\lambda_{5}=4.88127749135$, and the $5$-core, when it first appears, has about $0.538433561728\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{5})\geq 5)$ [1].

8.365340770047702714643014509591141846278719137911370579394156101303747243609249140526472559924021746

comment: The minimum is attained at $\lambda_{6}=6.32250555103$, and the $6$-core, when it first appears, has about $0.604638182695\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{6})\geq 6)$ [1].

9.875290724843900398166931013481935649636727369861392447711159365654956909177306398399832460695926528

comment: The minimum is attained at $\lambda_{7}=7.72458360044$, and the $7$-core, when it first appears, has about $0.651844404355\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{7})\geq 7)$ [1].

11.34412889749009164633003354367252165775865248752217016298709432771144857325090293197553885467849478

comment: The minimum is attained at $\lambda_{8}=9.09734440258$, and the $8$-core, when it first appears, has about $0.687379687246\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{8})\geq 8)$ [1].

12.78109969599954770002045814494717548620686258246512732253447340375314869612112335175524027145625145

comment: The minimum is attained at $\lambda_{9}=10.4470306813$, and the $9$-core, when it first appears, has about $0.715208555100\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{9})\geq 9)$ [1].

10:

14.19238948538860551267157564263474164395196391020752665260015321888975561150902701183531116626376871

comment: The minimum is attained at $\lambda_{10}=11.7779066065$, and the $10$-core, when it first appears, has about $0.737666502714\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{10})\geq 10)$ [1].

11:

15.58238546277987394793632721893316729376409298688945183299417284087190893736485161005949680380499953

comment: The minimum is attained at $\lambda_{11}=13.0930424983$, and the $11$-core, when it first appears, has about $0.756221714358\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{11})\geq 11)$ [1].

12:

16.95433608082373067537145274656211915227107450158198530770797599423654739794564896542024685566994089

comment: The minimum is attained at $\lambda_{12}=14.3947389019$, and the $12$-core, when it first appears, has about $0.771845397666\,n$ vertices, the fraction being $\mathbb{P}(\mathrm{Po}(\lambda_{12})\geq 12)$ [1].

Definition

The $k$-core of a graph [6] is its largest subgraph of minimum degree at least $k$. For $k\geq3$, the $k$-core threshold $c_k$ is the number such that the Erdős–Rényi random graph [7] $G(n,p)$ with $p=c/n$ has, with probability tending to $1$ as $n\to\infty$, an empty $k$-core when $c<c_k$ and a $k$-core on a positive fraction of the vertices when $c>c_k$; it equals $\min_{\lambda>0}\lambda/\mathbb{P}(\mathrm{Po}(\lambda)\geq k-1)$, with $\mathrm{Po}(\lambda)$ a Poisson variable of mean $\lambda$ [1].

Parameters

$k$

— minimum degree of the core ($k\geq3$)

Formulas

(1)

$c_k=\min_{\lambda>0}\frac{\lambda}{\mathbb{P}(\mathrm{Po}(\lambda)\geq k-1)} =\min_{\lambda>0}\frac{\lambda}{1-e^{-\lambda}\sum_{j=0}^{k-2}\lambda^j/j!}$ for $k\geq3$ [1].

(2)

The minimiser $\lambda_k$ is the unique positive zero of $g(\lambda)=\mathbb{P}(\mathrm{Po}(\lambda)\geq k-1)-\frac{e^{-\lambda}\lambda^{k-1}}{(k-2)!}$, the numerator of the derivative of $\lambda/\mathbb{P}(\mathrm{Po}(\lambda)\geq k-1)$, and $\lambda_k>k-2$: $g(0)=0$, $g(\lambda)\to1$ as $\lambda\to\infty$, and $g'(\lambda)=\frac{e^{-\lambda}\lambda^{k-2}(\lambda-k+2)}{(k-2)!}$, so $g$ decreases on $(0,k-2)$ and increases on $(k-2,\infty)$.

(3)

For $c>c_k$ the equation $\mu/\mathbb{P}(\mathrm{Po}(\mu)\geq k-1)=c$ has two positive roots, and with $\mu$ the larger one the $k$-core of $G(n,m)$, $m\sim cn/2$, has $\mathbb{P}(\mathrm{Po}(\mu)\geq k)\,n\,(1+o(1))$ vertices and $\frac{\mu}{2}\mathbb{P}(\mathrm{Po}(\mu)\geq k-1)\,n\,(1+o(1))$ edges with probability tending to $1$ [1] [4].

Comments

(4)

In $G(n,p)$ with $p=c/n$ and in $G(n,m)$ with $m=cn/2$ the average degree is about $c$, and the threshold is the same in both models [1] [3]. The $2$-core is different: a giant $2$-core grows together with the giant component from $c=1$ on, and the quotient $\lambda/\mathbb{P}(\mathrm{Po}(\lambda)\geq1)=\lambda/(1-e^{-\lambda})$ tends to $1$ as $\lambda\to0$ and increases with $\lambda$, so $c_2=1$ is an infimum that is not attained [4] [3]. For $k\geq3$ the minimum is attained at a unique $\lambda_k$ (2), and the $k$-core appears suddenly: at $c=c_k$ it already has about $\mathbb{P}(\mathrm{Po}(\lambda_k)\geq k)\,n$ vertices, $0.2676\,n$ for $k=3$ [1], and for $c>c_k$ its order is given by (3). The comment on each entry gives $\lambda_k$ and the fraction $\mathbb{P}(\mathrm{Po}(\lambda_k)\geq k)$ of the vertices in the newborn core.

(5)

Łuczak showed that for $k\geq3$ the $k$-core of $G(n,m)$ is either empty or on a positive fraction of the vertices [2]; Pittel, Spencer and Wormald located the threshold and proved the formula for $c_k$ [1], and shorter proofs were given by Cain and Wormald [4] and by Janson and Luczak [3]. The same minimisation, with the Poisson tail raised to the power $d-1$, gives the thresholds of $k$-cores in random $d$-uniform hypergraphs: with $m\sim cn/d$ edges the $k$-core appears at $c_{d,k}=\min_{\lambda>0}\lambda/\mathbb{P}(\mathrm{Po}(\lambda)\geq k-1)^{d-1}$ [5] [4], a minimum that is attained for every $k\geq2$ when $d\geq3$; for $d=3$ and $k=2$ it is $c_{3,2}=2.4554074822\ldots$, so the $2$-core of the random $3$-uniform hypergraph appears at $m/n=0.8184691607\ldots$.

Programs

(P1)

Python

from mpmath import mp, gammainc, findroot, exp, factorial
mp.dps = 30; k = 3
T = lambda x: gammainc(k - 1, 0, x, regularized=True)   # P(Po(x) >= k-1)
x = findroot(lambda x: T(x) - exp(-x)*x**(k-1)/factorial(k-2), k)
print(x / T(x))                                          # c_k

References

[1]

B. Pittel, J. Spencer and N. Wormald, Sudden emergence of a giant $k$-core in a random graph, Journal of Combinatorial Theory, Series B 67 (1996), 111–151.

[2]

T. Łuczak, Size and connectivity of the $k$-core of a random graph, Discrete Mathematics 91 (1991), 61–68.

[3]

S. Janson and M. J. Luczak, A simple solution to the $k$-core problem, Random Structures & Algorithms 30 (2007), 50–62. (arXiv)

[4]

J. Cain and N. Wormald, Encores on cores, Electronic Journal of Combinatorics 13 (2006), R81.

[5]

M. Molloy, Cores in random hypergraphs and Boolean formulas, Random Structures & Algorithms 27 (2005), 124–135.

Links

[6]

Wikipedia: Degeneracy (graph theory)

[7]

Wikipedia: Erdős–Rényi model

Similar tables

Pólya's random walk constants — probabilities of the simple random walk on lattices, indexed by dimension as this table is by the degree of the core

Diagonal Ramsey numbers — the extremal graph quantities in the database, with intervals where a value is known only to lie between two integers

Site and bond percolation thresholds of lattices — the thresholds at which a giant cluster appears in a random subgraph of a lattice, the lattice counterpart of the giant component of $G(n,c/n)$ at $c=1$

Data properties

Entries are of type: real number

How well the digits are known: proven

Sources of data: [1]

Table is complete: no (it holds $c_k$ for every $k$ with $3\leq k\leq12$)

How they were obtained:

Each entry is the value at the minimiser $\lambda_k$ of $f(\lambda)=\lambda/\mathbb{P}(\mathrm{Po}(\lambda)\geq k-1)$, computed in ball arithmetic with 64 guard bits beyond the 100 digits written.

That $\lambda_k$ is the unique minimiser and the minimum is global follows from the sign of $f'$, which is the sign of $g$ in (2): $g$ is negative on $(0,\lambda_k)$ and positive on $(\lambda_k,\infty)$, so $f$ decreases and then increases. The computation encloses $\lambda_k$ by bisection on the sign of $g$ between $k-2$ and $4k+10$, each sign decided in ball arithmetic, down to a bracket of half-width $10^{-106}$ whose ends are then checked to give $g$ opposite signs, and evaluates $f$ on that bracket as a ball; the Poisson tail is the finite sum $1-e^{-\lambda}\sum_{j<k-1}\lambda^j/j!$. Every ball has radius about $6\cdot10^{-106}$. Before any entry was written, all ten values were compared with a computation in mpmath at 120 digits that writes the tail as the regularised incomplete gamma function $\gamma(k-1,\lambda)/\Gamma(k-1)$ and finds the minimiser as a root of the numerical derivative of $f$, which agreed to the last written digit in every row; $c_3\approx3.35$ and the size $0.27\,n$ of the newborn $3$-core were compared with the values Pittel, Spencer and Wormald state.