{
  "id": "1805.05506",
  "version": "v1",
  "published": "2018-05-15T00:42:25.000Z",
  "updated": "2018-05-15T00:42:25.000Z",
  "title": "A bound on judicious bipartitions of directed graphs",
  "authors": [
    "Jianfeng Hou",
    "Huawen Ma",
    "Xingxing Yu",
    "Xia Zhang"
  ],
  "comment": "16 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously, which have received a lot of attentions lately. Scott asked the following natural question: What is the maximum constant $c_d$ such that every directed graph $D$ with $m$ arcs and minimum outdegree $d$ admits a bipartition $V(D)= V_1\\cup V_2$ satisfying $\\min\\{e(V_1, V_2), e(V_2, V_1)\\}\\ge c_d m$? Here, for $i=1,2$, $e(V_{i},V_{3-i})$ denotes the number of arcs in $D$ from $V_{i}$ to $V_{3-i}$. Lee, Loh, and Sudakov %[Judicious partitions of directed graphs, Random Struct. Alg. 48 %(2016) 147--170] conjectured that every directed graph $D$ with $m$ arcs and minimum outdegree at least $d\\ge 2$ admits a bipartition $V(D)=V_1\\cup V_2$ such that \\[ \\min\\{e(V_1,V_2),e(V_2,V_1)\\}\\geq \\Big(\\frac{d-1}{2(2d-1)}+ o(1)\\Big)m. \\] %While it is not known whether or not the minimum outdegree condition %alone is sufficient, w We show that this conjecture holds under the additional natural condition that the minimum indegree is also at least $d$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-15T00:42:25.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "directed graph",
      "judicious bipartitions",
      "additional natural condition",
      "minimum outdegree condition",
      "random struct"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}