A simple solution to the k‐core problem
From MaRDI portal
Publication:3419611
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.
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
Cites work
Cited in
(49)- Size and connectivity of the \(k\)-core of a random graph
- Finding density-based subspace clusters in graphs with feature vectors
- Loose cores and cycles in random hypergraphs
- Preferential attachment without vertex growth: emergence of the giant component
- Core forging and local limit theorems for the \(k\)-core of random graphs
- The diameter of weighted random graphs
- On the threshold for k-regular subgraphs of random graphs
- Degree sequences of monocore graphs
- A central limit theorem for diffusion in sparse random graphs
- The minimal k-core problem for modeling k-assemblies
- A general critical condition for the emergence of a giant component in random graphs with given degrees
- Cores of random graphs are born Hamiltonian
- Sets that are connected in two random graphs
- Random graphs with forbidden vertex degrees
- SIR epidemics on random graphs with a fixed degree sequence
- Small cores in 3-uniform hypergraphs
- Dismantling Sparse Random Graphs
- The probability that a random multigraph is simple
- A new approach to the giant component problem
- Diffusion and cascading behavior in random networks
- On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
- The cook-book approach to the differential equation method
- The solution space geometry of random linear equations
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- Dense peelable random uniform hypergraphs
- Persuasion in networks: public signals and cores
- Degree correlations in scale-free random graph models
- Law of large numbers for the SIR epidemic on a random graph with given degrees
- Thek-Core and Branching Processes
- On the spread of random graphs
- A new approach to the orientation of random hypergraphs
- The stripping process can be slow. II
- Singularity of the \(k\)-core of a random graph
- Load Thresholds for Cuckoo Hashing with Overlapping Blocks
- Successive minimum spanning trees
- The coreness and H-index of random geometric graphs
- How to determine if a random graph with a fixed degree sequence has a giant component
- Degree-penalized contact processes
- On edge collapse of random simplicial complexes
- Peeling close to the orientability threshold. Spatial coupling in hashing-based data structures
- ShockHash: near optimal-space minimal perfect hashing beyond brute-force
- Insertion time of random walk cuckoo hashing below the peeling threshold
- Component games on random graphs
- The critical Karp-Sipser core of random graphs
- The k-XORSAT threshold revisited (extended abstract)
- The k-core in percolated dense graph sequences
- Asymptotic optimality of degree-greedy discovering of independent sets in configuration model graphs
- On the robustness of random k-cores
- Asymptotic normality of the \(k\)-core in random graphs
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)
