2011/02/28 by Mamadou Moustapha Kanté
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Discrete mathematics #Finite Group Theory Research #Mathematical analysis #Mathematics #Matrix (chemical analysis) #Matroid #Rank (graph theory) #Sequence (biology) #acm:05C22 #acm:05C50 #acm:05C75 #acm:68R05 #acm:68R10 #cs.DM #graph theory and CDMA systems #math.CO #msc:05C22 #msc:05C50 #msc:05C75 #msc:68R05 #msc:68R10
paper · pdf · doi:10.1016/j.ejc.2012.03.034
published as European Journal of Combinatorics 33(8):1820--1841(2012) · 35 pages. Revised version with a section for directed graphs
openalex publication_date 2012/05/28 · arxiv created 2014/07/08 · arxiv updated 2014/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In [Rank-Width and Well-Quasi-Ordering of Skew-Symmetric or Symmetric Matrices, arXiv:1007.3807v1] Oum proved that, for a fixed finite field F, any infinite sequence M1,M2,... of (skew) symmetric matrices over F of bounded F-rank-width has a pair i< j, such that Mi is isomorphic to a principal submatrix of a principal pivot transform of Mj. We generalise this result to σ-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 σ-symmetric matrices. As a by-product, we obtain that for every infinite sequence G1,G2,... of directed graphs of bounded rank-width there exist a pair i<j such that Gi is a pivot-minor of Gj. Another consequence is that non-singular principal submatrices of a σ-symmetric matrix form a delta-matroid. We extend in this way the notion of representability of delta-matroids by Bouchet.