{
  "id": "1304.2016",
  "version": "v1",
  "published": "2013-04-07T16:19:27.000Z",
  "updated": "2013-04-07T16:19:27.000Z",
  "title": "First critical probability for a problem on random orientations in $G(n,p)$",
  "authors": [
    "Sven Erick Alm",
    "Svante Janson",
    "Svante Linusson"
  ],
  "comment": "15 pages, 3 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We study the random graph $G(n,p)$ with a random orientation. For three fixed vertices $s,a,b$ in $G(n,p)$ we study the correlation of the events $a \\to s$ and $s\\to b$. We prove that asymptotically the correlation is negative for small $p$, $p<\\frac{C_1}n$, where $C_1\\approx0.3617$, positive for $\\frac{C_1}n<p<\\frac2n$ and up to $p=p_2(n)$. Computer aided computations suggest that $p_2(n)=\\frac{C_2}n$, with $C_2\\approx7.5$. We conjecture that the correlation then stays negative for $p$ up to the previously known zero at $\\frac12$; for larger $p$ it is positive.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-04-07T16:19:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60C05",
      "60K35"
    ],
    "keywords": [
      "first critical probability",
      "random orientation",
      "correlation",
      "computer aided computations",
      "random graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1304.2016E"
    }
  }
}