Birth of a giant $(k_1,k_2)$-core in the random digraph
| Autor: | Pittel, Boris, Poole, Dan |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The $(k_1,k_2)$-core of a digraph is the largest sub-digraph with minimum in-degree and minimum out-degree at least $k_1$ and $k_2$ respectively. For $\max\{k_1, k_2\} \geq 2$, we establish existence of the threshold edge-density $c^*=c^*(k_1,k_2)$, such that the random digraph $D(n,m)$, on the vertex set $[n]$ with $m$ edges, asymptotically almost surely has a giant $(k_1,k_2)$-core if $m/n> c^*$, and has no $(k_1,k_2)$-core if $m/n |
| Databáze: | arXiv |
| Externí odkaz: |
|