Well-quasi-ordering of matrices under Schur complement and applications to directed graphs

DOI10.1016/J.EJC.2012.03.034MaRDI QIDQ449209zbMATH OpenOpenAlexFDO

Authors Mamadou Moustapha Kanté

Publication date 12 September 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.2134

zbMATH Keywords

principal pivot transformpivot-minorprincipal submatrixdelta-matroidsequence of directed graphsskew symmetric matrices

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Hermitian, skew-Hermitian, and related matrices (15B57) Combinatorial aspects of matroids and geometric lattices (05B35)

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 $mathbfF$, any infinite sequence $M_1,M_2,\mathrm{...}$ of (skew) symmetric matrices over $mathbfF$ of bounded $mathbfF$-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,\mathrm{...}$ 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.

Recommendations

• Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices (extended abstract)
• Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
• scientific article; zbMATH DE number 741201
• Rank-width and Well-quasi-ordering of Skew-symmetric Matrices
• Rank-Width and Well-Quasi-Ordering

Cites work

• scientific article; zbMATH DE number 3156382 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3365295 (Why is no real title available?)
• Approximating clique-width and branch-width
• Branch-width and well-quasi-ordering in matroids and graphs.
• Finding Branch-Decompositions and Rank-Decompositions
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. XX: Wagner's conjecture
• Graph operations characterizing rank-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Greedy algorithm and symmetric matroids
• Handle-rewriting hypergraph grammars
• Isotropic systems
• Maximal pivots on graphs with an application to gene assembly
• Principal pivot transforms: Properties and applications
• Rank-Width and Well-Quasi-Ordering
• Rank-width and vertex-minors
• Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices
• The rank-width of edge-coloured graphs
• Towards a matroid-minor structure theory

Cited in

(7)

• Rank-width: algorithmic and structural results
• Digraphs of bounded width
• The rank-width of edge-coloured graphs
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Rank-width and Well-quasi-ordering of Skew-symmetric Matrices
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
• Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices

This page was built for publication: Well-quasi-ordering of matrices under Schur complement and applications to directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q449209)