{
  "id": "1609.01003",
  "version": "v1",
  "published": "2016-09-05T00:14:09.000Z",
  "updated": "2016-09-05T00:14:09.000Z",
  "title": "Connections in randomly oriented graphs",
  "authors": [
    "Bhargav Narayanan"
  ],
  "comment": "6 pages, submitted",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Given an undirected graph $G$, let us randomly orient $G$ by tossing independent (possibly biased) coins, one for each edge of $G$. Writing $a\\rightarrow b$ for the event that there exists a directed path from a vertex $a$ to a vertex $b$ in such a random orientation, we prove that $\\mathbb{P}(s\\rightarrow a \\cap s\\rightarrow b) \\ge \\mathbb{P}(s\\rightarrow a) \\mathbb{P}(s\\rightarrow b)$ for any three vertices $s$, $a$ and $b$ of $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-09-05T00:14:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60K35"
    ],
    "keywords": [
      "randomly oriented graphs",
      "connections",
      "random orientation",
      "tossing independent"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}