Small forbidden configurations
type: Item
instance of: scholarly article
title: Small forbidden configurations
zbMATH Open document ID: 0878.05019
DOI: 10.1007/BF03352989
author: J. Griggs
author: Attila Sali
author: R. P. Anstee
published in: Graphs and Combinatorics
publication date: 1997-12-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05B30
zbMATH DE Number: 1029263
zbMATH Keywords: forbidden configuration
zbMATH Keywords: simple matrix
zbMATH Keywords: general bound
MaRDI profile type: Publication
cites work: General forbidden configuration theorems
cites work: Forbidden submatrices
cites work: A forbidden configuration theorem of Alon
cites work: Forbidden configurations, discrepancy and determinants
cites work: Forbidden configurations: Induction and linear algebra
cites work: On the trace of finite sets
cites work: Bounding one-way differences
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
full work available at URL: https://doi.org/10.1007/bf03352989
OpenAlex ID: W2051905988
description: scientific article; zbMATH DE number 1029263