K-core in percolated dense graph sequences

Authors Erhan Bayraktar, Suman Chakraborty, Xin Zhang

Publication date 17 December 2020

Abstract: We determine the size of

k

-core in a large class of dense graph sequences. Let

G_{n}

be a sequence of undirected,

n

-vertex graphs with edge weights

{a_{i, j}^{n}}_{i, j i n [n]}

that converges to a kernel

W : [0, 1]^{2} o [0, + i n f t y)

in the cut metric. Keeping an edge

(i, j)

of

G_{n}

with probability

m i n a_{i, j}^{n} / n, 1

independently, we obtain a sequence of random graphs

G_{n} (f r a c 1 n)

. Denote by

m a t h c a l A

the property of a branching process that the initial particle has at least

k

children, each of which has at least

k - 1

children, each of which has at least

k - 1

children, and so on. Using branching process and the theory of dense graph limits, under mild assumptions we obtain the size of

k

-core of random graphs

G_{n} (f r a c 1 n)

, �egin{align*} ext{size of

k

-core of } G_nleft(frac{1}{n} ight) =n mathbb{P}_{X^W}left(mathcal{A} ight) +o_p(n). end{align*} Our result can also be used to obtain the threshold of appearance of a

k

-core of order

n

.

This page was built for publication: K-core in percolated dense graph sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356360)