Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices

Cited 5 time in webofscience Cited 0 time in scopus
  • Hit : 341
  • Download : 0
We prove that every infinite sequence of skew-symmetric or symmetric matrices M-1, M-2, ... over a fixed finite field must have a pair M-i, M-j (i < j) such that M-i is isomorphic to a principal submatrix of the Schur complement of a nonsingular principal submatrix in M-j, if those matrices have bounded rank-width. This generalizes three theorems on well-quasi-ordering of graphs or matroids admitting good tree-like decompositions; (1) Robertson and Seymour's theorem for graphs of bounded tree-width, (2) Geelen, Gerards, and Whittle's theorem for matroids representable over a fixed finite field having bounded branch-width, and (3) Oum's theorem for graphs of bounded rank-width with respect to pivot-minors. (C) 2011 Elsevier Inc. All rights reserved.
Publisher
ELSEVIER SCIENCE INC
Issue Date
2012-04
Language
English
Article Type
Article
Keywords

GRAPH MINORS; BRANCH-WIDTH; TREE-WIDTH; MATROIDS; THEOREM

Citation

LINEAR ALGEBRA AND ITS APPLICATIONS, v.436, no.7, pp.2008 - 2036

ISSN
0024-3795
DOI
10.1016/j.laa.2011.09.027
URI
http://hdl.handle.net/10203/98993
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 5 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0