{
  "id": "math/0702147",
  "version": "v1",
  "published": "2007-02-06T16:02:48.000Z",
  "updated": "2007-02-06T16:02:48.000Z",
  "title": "Cycles in dense digraphs",
  "authors": [
    "Maria Chudnovsky",
    "Paul Seymour",
    "Blair D. Sullivan"
  ],
  "journal": "Combinatorica 28 2008 1-18",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let G be a digraph (without parallel edges) such that every directed cycle has length at least four; let $\\beta(G)$ denote the size of the smallest subset X in E(G) such that $G\\X$ has no directed cycles, and let $\\gamma(G)$ be the number of unordered pairs {u,v} of vertices such that u,v are nonadjacent in G. It is easy to see that if $\\gamma(G) = 0$ then $\\beta(G) = 0$; what can we say about $\\beta(G)$ if $\\gamma(G)$ is bounded? We prove that in general $\\beta(G)$ is at most $\\gamma(G)$. We conjecture that in fact $\\beta(G)$ is at most $\\gamma(G)/2$ (this would be best possible if true), and prove this conjecture in two special cases: 1. when V(G) is the union of two cliques, 2. when the vertices of G can be arranged in a circle such that if distinct u,v,w are in clockwise order and uw is a (directed) edge, then so are both uv and vw.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2007-02-06T16:02:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "dense digraphs",
      "directed cycle",
      "parallel edges",
      "conjecture",
      "special cases"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007math......2147C"
    }
  }
}