{
  "id": "1102.2134",
  "version": "v3",
  "published": "2011-02-10T14:52:45.000Z",
  "updated": "2014-07-08T11:34:53.000Z",
  "title": "Well-Quasi-Ordering of Matrices under Schur Complement and Applications to Directed Graphs",
  "authors": [
    "Mamadou Moustapha Kanté"
  ],
  "comment": "35 pages. Revised version with a section for directed graphs",
  "journal": "European Journal of Combinatorics 33(8):1820--1841(2012)",
  "doi": "10.1016/j.ejc.2012.03.034",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In [Rank-Width and Well-Quasi-Ordering of Skew-Symmetric or Symmetric Matrices, arXiv:1007.3807v1] Oum proved that, for a fixed finite field $\\mathbf{F}$, any infinite sequence $M_1,M_2,...$ of (skew) symmetric matrices over $\\mathbf{F}$ of bounded $\\mathbf{F}$-rank-width has a pair $i< j$, such that $M_i$ is isomorphic to a principal submatrix of a principal pivot transform of $M_j$. We generalise this result to $\\sigma$-symmetric matrices introduced by Rao and myself in [The Rank-Width of Edge-Coloured Graphs, arXiv:0709.1433v4]. (Skew) symmetric matrices are special cases of $\\sigma$-symmetric matrices. As a by-product, we obtain that for every infinite sequence $G_1,G_2,...$ of directed graphs of bounded rank-width there exist a pair $i<j$ such that $G_i$ is a pivot-minor of $G_j$. Another consequence is that non-singular principal submatrices of a $\\sigma$-symmetric matrix form a delta-matroid. We extend in this way the notion of representability of delta-matroids by Bouchet.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-07-08T11:34:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R05",
      "68R10",
      "05C22",
      "05C50",
      "05C75",
      "F.0",
      "G.2.1",
      "G.2.2"
    ],
    "keywords": [
      "symmetric matrices",
      "directed graphs",
      "schur complement",
      "applications",
      "infinite sequence"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1102.2134M"
    }
  }
}