{
  "id": "1608.05095",
  "version": "v1",
  "published": "2016-08-17T20:31:29.000Z",
  "updated": "2016-08-17T20:31:29.000Z",
  "title": "Birth of a giant $(k_1,k_2)$-core in the random digraph",
  "authors": [
    "Boris Pittel",
    "Dan Poole"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "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<c^*$. Specifically, denoting $\\text{P}(\\text{Poisson}(z)\\ge k)$ by $p_k(z)$, we prove that $c^*=\\min\\limits_{z_1,z_2}\\max\\left\\{\\tfrac{z_1}{p_{k_1}(z_1)p_{k_2-1}(z_2)}; \\tfrac{z_2}{p_{k_1-1}(z_1)p_{k_2}(z_2)}\\right\\}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-08-17T20:31:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "05C80",
      "05C05",
      "34E05",
      "60C05"
    ],
    "keywords": [
      "random digraph",
      "vertex set",
      "minimum in-degree",
      "largest sub-digraph",
      "minimum out-degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}