Linear algebra methods for Forbidden configurations (Q653981): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 09:51, 30 January 2024

scientific article
Language Label Description Also known as
English
Linear algebra methods for Forbidden configurations
scientific article

    Statements

    Linear algebra methods for Forbidden configurations (English)
    0 references
    0 references
    0 references
    20 December 2011
    0 references
    A matrix is called simple if it is a \((0,1)\) matrix with no repeated columns. Let \(F\) be a \(k\times n\) \((0,1)\) matrix, and let forb\((m,F)\) stand for the largest number of columns in an \(m\)-rowed simple matrix for which no \(k\times n\) submatrix is a row and column permutation of \(F.\) It has been shown that if \(F\) is a \(k\)-rowed matrix then forb\((m,F)\) is \(O(m^{k}).\) In the paper all \(k\)-rowed matrices \(F\) for which forb\((m,F)\) is \(O(m^{k-1})\) and for which forb\((m,F)\) is \(\Theta (m^{k})\) are characterized.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    Forbidden configurations
    0 references
    forbidden trace
    0 references