{
  "id": "1412.6201",
  "version": "v1",
  "published": "2014-12-19T02:53:57.000Z",
  "updated": "2014-12-19T02:53:57.000Z",
  "title": "An Upper Bound on the Size of Obstructions for Bounded Linear Rank-Width",
  "authors": [
    "Mamadou Moustapha Kanté",
    "O-joung Kwon"
  ],
  "comment": "28 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "We provide a doubly exponential upper bound in $p$ on the size of forbidden pivot-minors for symmetric or skew-symmetric matrices over a fixed finite field $\\mathbb{F}$ of linear rank-width at most $p$. As a corollary, we obtain a doubly exponential upper bound in $p$ on the size of forbidden vertex-minors for graphs of linear rank-width at most $p$. This solves an open question raised by Jeong, Kwon, and Oum [Excluded vertex-minors for graphs of linear rank-width at most $k$. European J. Combin., 41:242--257, 2014]. We also give a doubly exponential upper bound in $p$ on the size of forbidden minors for matroids representable over a fixed finite field of path-width at most $p$. Our basic tool is the pseudo-minor order used by Lagergren [Upper Bounds on the Size of Obstructions and Interwines, Journal of Combinatorial Theory Series B, 73:7--40, 1998] to bound the size of forbidden graph minors for bounded path-width. To adapt this notion into linear rank-width, it is necessary to well define partial pieces of graphs and merging operations that fit to pivot-minors. Using the algebraic operations introduced by Courcelle and Kant\\'e, and then extended to (skew-)symmetric matrices by Kant\\'e and Rao, we define boundaried $s$-labelled graphs and prove similar structure theorems for pivot-minor and linear rank-width.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-19T02:53:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75",
      "G.2.2"
    ],
    "keywords": [
      "bounded linear rank-width",
      "doubly exponential upper bound",
      "obstructions",
      "fixed finite field",
      "similar structure theorems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.6201M"
    }
  }
}