Small forbidden configurations (Q1359370): Difference between revisions

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.