Sudden emergence of a giant \(k\)-core in a random graph (Q1924140): Difference between revisions
From MaRDI portal
Removed claims |
Created claim: Wikidata QID (P12): Q106185259, #quickstatements; #temporary_batch_1711094041063 |
||
(5 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Boris G. Pittel / rank | |||
Normal rank | |||
Property / author | |||
Property / author: J. H. Spencer / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Gregory Loren McColm / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1996.0036 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2065663455 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q106185259 / rank | |||
Normal rank |
Latest revision as of 13:32, 22 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sudden emergence of a giant \(k\)-core in a random graph |
scientific article |
Statements
Sudden emergence of a giant \(k\)-core in a random graph (English)
0 references
14 October 1996
0 references
The \(k\)-core of a graph is the largest subgraph of minimum degree \(\geq k\). Fix \(\delta\in(0,1)\), and let \(k\geq 3\); there is a \(\gamma_k\) and a \(p_k\) such that the following is true. For a random graph of \(n\) edges and \(m\) vertices, when \(m<\gamma_kn-n^{1-\delta}\), the \(k\)-core a. s. has \(o(n)\) vertices, while if \(m>\gamma_k+n^{1-\delta}\), the \(k\)-core a. s. has at least \(p_kn+o(n)\) vertices. And it's unlikely that you'll catch the graph in transition: even if \(|\gamma_kn-m|\leq n^{1-\delta}\), such a graph a. s. has a \(k\)-core of \(o(n)\) edges or \(p_k(n)n+o(n)\) edges. The difficult proof is in two parts. In the first, the authors consider a process that successively deletes edges adjacent to vertices of degree \(<k\); they link this process with a parameter, and show that a random process based on the parameter alone simulates the graph process and is nearly Markov. In the second, they use this process to estimate the size of the \(k\)-cores.
0 references
\(k\)-core
0 references
subgraph
0 references
minimum degree
0 references
random graph
0 references
random process
0 references