Small forbidden configurations
In the present paper small forbidden configurations (or submatrices) of \((0,1)\)-matrices are researched. An \(m \times n\) \((0,1)\)-matrix with no repeated columns is called simple. The maximum number of columns of a simple matrix \(A\) of \(m\) rows with no configuration \(F\) will be denoted by \(\text{forb} (m,F).\) The authors present several results concerning forbidden configurations of two and three rows and obtain linear, quadratic and cubic bounds. In particular, the following results have been obtained: Theorem 2.4. Let \(F= \left[\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix} \right].\) Then \(\text{forb} (m,F)=m+2\). Theorem 2.6. Let \(F_0= \left[\begin{matrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \end{matrix} \right].\) Then \( \lfloor {m^2 \over 4}\rfloor+m+1 \leq \text{forb} (m,F_0) \leq \lfloor {m^2 \over 4}\rfloor+\lfloor{3 \over 2}m\rfloor .\) Theorem 3.10. Let \(F\) be \([2K^2_3K^0_3]\) or \([2K^2_3K^1_3].\) Then for \(m \geq 3\), \(\text{forb} (m,F)\geq ({m\over3}+1)^3.\) Where \(K_k\) denotes the \(k\times 2^k\) submatrix of all possible columns of size \(k\), and \(K^r_n\) denotes the \(n\times 2^n\) submatrix of all columns having \(r\) ones.
- A combinatorial problem; stability and order for models and theories in infinitary languages
- A forbidden configuration theorem of Alon
- Bounding one-way differences
- Forbidden configurations, discrepancy and determinants
- Forbidden configurations: Induction and linear algebra
- Forbidden submatrices
- General forbidden configuration theorems
- On the density of families of sets
- On the trace of finite sets
- Small forbidden configurations. III.
- Matrices with forbidden subconfigurations
- Forbidden submatrices
- A forbidden configuration theorem of Alon
- Small forbidden configurations. II
- Geometric graphs with no self-intersecting path of length three
- Forbidden configurations: Induction and linear algebra
- A survey of forbidden configuration results
- Multi-symbol forbidden configurations
- Forbidden families of minimal quadratic and cubic configurations
- Small forbidden configurations. IV: The 3 rowed case
- Forbidden configurations: boundary cases
- Forbidden configurations: boundary cases
- Small forbidden configurations. V: Exact bounds for 4 2 cases
- On minimum saturated matrices
- Evidence for a forbidden configuration conjecture: One more case solved
- Forbidden configurations and product constructions
- Exponential multivalued forbidden configurations
- Forbidden Berge hypergraphs
- Forbidden configurations and repeated induction
- Linear algebra methods for Forbidden configurations
- Genetic algorithms applied to problems of forbidden configurations
- Forbidden configurations and Steiner designs
- Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis
- Pairwise intersections and forbidden configurations
- Forbidden configurations: exact bounds determined by critical substructures
This page was built for publication: Small forbidden configurations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1359370)
