{
  "id": "2212.09188",
  "version": "v1",
  "published": "2022-12-18T23:02:24.000Z",
  "updated": "2022-12-18T23:02:24.000Z",
  "title": "Problems, proofs, and disproofs on the inversion number",
  "authors": [
    "Guillaume Aubian",
    "Frédéric Havet",
    "Florian Hörsch",
    "Felix Klingelhoefer",
    "Nicolas Nisse",
    "Clément Rambaud",
    "Quentin Vermande"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The {\\it inversion} of a set $X$ of vertices in a digraph $D$ consists in reversing the direction of all arcs of $D\\langle X\\rangle$. The {\\it inversion number} of an oriented graph $D$, denoted by ${\\rm inv}(D)$, is the minimum number of inversions needed to transform $D$ into an acyclic oriented graph. In this paper, we study a number of problems involving the inversion number of oriented graphs. Firstly, we give bounds on ${\\rm inv}(n)$, the maximum of the inversion numbers of the oriented graphs of order $n$. We show $n - \\mathcal{O}(\\sqrt{n\\log n}) \\ \\leq \\ {\\rm inv}(n) \\ \\leq \\ n - \\lceil \\log (n+1) \\rceil$. Secondly, we disprove a conjecture of Bang-Jensen et al. asserting that, for every pair of oriented graphs $L$ and $R$, we have ${\\rm inv}(L\\Rightarrow R) ={\\rm inv}(L) + {\\rm inv}(R)$, where $L\\Rightarrow R$ is the oriented graph obtained from the disjoint union of $L$ and $R$ by adding all arcs from $L$ to $R$. Finally, we investigate whether, for all pairs of positive integers $k_1,k_2$, there exists an integer $f(k_1,k_2)$ such that if $D$ is an oriented graph with ${\\rm inv}(D) \\geq f(k_1,k_2)$ then there is a partition $(V_1, V_2)$ of $V(D)$ such that ${\\rm inv}(D\\langle V_i\\rangle) \\geq k_i$ for $i=1,2$. We show that $f(1,k)$ exists and $f(1,k)\\leq k+10$ for all positive integers $k$. Further, we show that $f(k_1,k_2)$ exists for all pairs of positive integers $k_1,k_2$ when the oriented graphs in consideration are restricted to be tournaments.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-12-18T23:02:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "inversion number",
      "positive integers",
      "acyclic oriented graph",
      "disjoint union",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}