Linear algebra methods for Forbidden configurations
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.
- A combinatorial problem; stability and order for models and theories in infinitary languages
- Counterexample to the Frankl-Pach conjecture for uniform, dense families
- Disjoint representability of sets and their complements
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Forbidding complete hypergraphs as traces
- scientific article; zbMATH DE number 5763169 (Why is no real title available?)
- scientific article; zbMATH DE number 736296 (Why is no real title available?)
- On disjointly representable sets
- On the density of families of sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On the VC-dimension of uniform hypergraphs
- Small forbidden configurations
- Small forbidden configurations. IV: The 3 rowed case
- Traces of uniform families of sets
- Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis
- Unavoidable traces of set systems
- Small forbidden configurations. III.
- Matrices with forbidden subconfigurations
- Forbidden configurations: Induction and linear algebra
- Small forbidden configurations. IV: The 3 rowed case
- Forbidden configurations: boundary cases
- Matrices with forbidden submatrices
- Multivalued matrices and forbidden configurations
- Genetic algorithms applied to problems of forbidden configurations
- Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis
This page was built for publication: Linear algebra methods for Forbidden configurations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653981)
