A simple solution to the k‐core problem

DOI10.1002/RSA.20147zbMATH Open1113.05091arXivmath/0508453OpenAlexW2330524492MaRDI QIDQ3419611FDOQ3419611

Authors: Svante Janson, Malwina Luczak 

Publication date: 7 February 2007

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We study the k-core of a random (multi)graph on n vertices with a given degree sequence. We let n tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the k-core is empty, and other conditions that imply that with high probability the k-core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer and Wormald on the existence and size of a k-core in G(n,p) and G(n,m). Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs.

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

Recommendations

• Minimum k‐cores and the k‐core polytope
• The \(k\)-separator problem
• The \(k\)-partitioning problem
• A complete resolution of the Keller maximum clique problem
• The $k$ -Equal Problem
• The minimal \(k\)-core problem for modeling \(k\)-assemblies
• A Linear Time Algorithm for Finding ak-Tree Core
• scientific article; zbMATH DE number 1092062
• The \(k\)-cardinality assignment problem
• A parameterized complexity view on collapsing \(k\)-cores

zbMATH Keywords

law of large numbersempirical distributionsdeath processesCores of random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Strong limit theorems (60F15) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Vertex degrees (05C07)

Cites Work

• Title not available (Why is that?)
• The probability that a random multigraph is simple
• Title not available (Why is that?)
• Poisson Cloning Model for Random Graphs

Cited In (38)

• Singularity of the \(k\)-core of a random graph
• Persuasion in networks: public signals and cores
• Random graphs with forbidden vertex degrees
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• On the threshold for \(k\)-regular subgraphs of random graphs
• Preferential attachment without vertex growth: emergence of the giant component
• Successive minimum spanning trees
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• The minimal \(k\)-core problem for modeling \(k\)-assemblies
• SIR epidemics on random graphs with a fixed degree sequence
• Diffusion and cascading behavior in random networks
• Dismantling Sparse Random Graphs
• The probability that a random multigraph is simple
• The diameter of weighted random graphs
• On the robustness of random \(k\)-cores
• Asymptotic normality of the \(k\)-core in random graphs
• Cores of random graphs are born Hamiltonian
• A general critical condition for the emergence of a giant component in random graphs with given degrees
• Thek-Core and Branching Processes
• The cook-book approach to the differential equation method
• Law of large numbers for the SIR epidemic on a random graph with given degrees
• The coreness and H-index of random geometric graphs
• Small cores in 3-uniform hypergraphs
• Sets that are connected in two random graphs
• Degree sequences of monocore graphs
• Finding density-based subspace clusters in graphs with feature vectors
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• The solution space geometry of random linear equations
• A central limit theorem for diffusion in sparse random graphs
• On the spread of random graphs
• Core forging and local limit theorems for the \(k\)-core of random graphs
• A new approach to the giant component problem
• Title not available (Why is that?)
• The stripping process can be slow. II
• Degree correlations in scale-free random graph models
• A new approach to the orientation of random hypergraphs
• Loose cores and cycles in random hypergraphs
• How to determine if a random graph with a fixed degree sequence has a giant component

This page was built for publication: A simple solution to the k‐core problem

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