Thek-Core and Branching Processes

DOI10.1017/S0963548307008589zbMATH Open1136.05071arXivmath/0511093MaRDI QIDQ5448993FDOQ5448993

Authors: Oliver Riordan 

Publication date: 10 March 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: The k-core of a graph G is the maximal subgraph of G having minimum degree at least k. In 1996, Pittel, Spencer and Wormald found the threshold $lambd{a}_c$ for the emergence of a non-trivial k-core in the random graph $G(n,lambda/n)$, and the asymptotic size of the k-core above the threshold. We give a new proof of this result using a local coupling of the graph to a suitable branching process. This proof extends to a general model of inhomogeneous random graphs with independence between the edges. As an example, we study the k-core in a certain power-law or `scale-free' graph with a parameter c controlling the overall density of edges. For each k at least 3, we find the threshold value of c at which the k-core emerges, and the fraction of vertices in the k-core when c is epsilon above the threshold. In contrast to $G(n,lambda/n)$, this fraction tends to 0 as epsilon tends to 0.

Full work available at URL: https://arxiv.org/abs/math/0511093

Recommendations

• Sudden emergence of a giant \(k\)-core in a random graph
• Core forging and local limit theorems for the \(k\)-core of random graphs
• Asymptotic normality of the \(k\)-core in random graphs
• Size and connectivity of the \(k\)-core of a random graph
• How does the core sit inside the mantle?

zbMATH Keywords

power-lawscale-free graphGalton-Watson branching processRandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Vertex degrees (05C07)

Cites Work

• Emergence of Scaling in Random Networks
• The phase transition in inhomogeneous random graphs
• Sudden emergence of a giant \(k\)-core in a random graph
• The phase transition in the uniformly grown random graph has infinite order
• A simple solution to the k‐core problem
• A Random Graph Model for Power Law Graphs
• Cores in random hypergraphs and Boolean formulas
• Families of Non-disjoint subsets
• The Small Giant Component in Scale-Free Random Graphs

Cited In (24)

• Propagation of chaos of forward-backward stochastic differential equations with graphon interactions
• Singularity of the \(k\)-core of a random graph
• The structure of typical clusters in large sparse random configurations
• Random graphs with forbidden vertex degrees
• Continuous phase transitions on Galton–Watson trees
• Branching Processes, the Max-Plus Algebra and Network Calculus
• \(k\)-core organization in complex networks
• A branching process with deletions and mergers that matches the threshold for hypercube percolation
• An old approach to the giant component problem
• Survival probabilities for \(N\)-ary subtrees on a Galton-Watson family tree
• Phase transitions in graphs on orientable surfaces
• On the robustness of random \(k\)-cores
• Asymptotic normality of the \(k\)-core in random graphs
• Cores of random graphs are born Hamiltonian
• How does the core sit inside the mantle?
• The cook-book approach to the differential equation method
• The coreness and H-index of random geometric graphs
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• Random simplicial complexes: around the phase transition
• A central limit theorem for diffusion in sparse random graphs
• Core forging and local limit theorems for the \(k\)-core of random graphs
• The stripping process can be slow. II
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
• Loose cores and cycles in random hypergraphs

This page was built for publication: Thek-Core and Branching Processes

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