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

DOI10.1016/J.EJC.2012.03.034zbMATH Open1269.05045arXiv1102.2134OpenAlexW2046637099MaRDI QIDQ449209FDOQ449209

Authors: Mamadou Moustapha Kanté 

Publication date: 12 September 2012

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

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.

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

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

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)

Cites Work

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

Cited In (7)

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

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)