Small forbidden configurations. III. (Q1010642)

Summary: The present paper continues the work begun by Anstee, Ferguson, Griggs and Sali on small forbidden configurations [\textit{R. Anstee}, \textit{J.R. Griggs}, and \textit{A. Sali}, ``Small forbidden configurations'', Graphs Comb. 13, No.\,2, 97--118 (1997; Zbl 0878.05019); \textit{R. Anstee}, \textit{R. Ferguson}, and \textit{A. Sali}, ``Small forbidden configurations. II'', Electron. J. Comb. 8, No.\,1, Res. paper R4 (2001; Zbl 0960.05100); \textit{R. Anstee} and \textit{A. Sali}, ``Small forbidden configurations. IV: The 3 rowed case'', Combinatorica 25, No.\,5, 503--518 (2005; Zbl 1107.05090)]. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. Let \(F\) be a \(k\times l\) (0,1)-matrix (the forbidden configuration). Assume \(A\) is an \(m\times n\) simple matrix which has no submatrix which is a row and column permutation of \(F\). We define forb \((m,F)\) as the largest \(n\), which would depend on \(m\) and \(F\), so that such an \(A\) exists. `Small' refers to the size of \(k\) and in this paper \(k=2\). For \(p\leq q\), we set \(F_{pq}\) to be the \(2\times (p+q)\) matrix with \(p[\binom{1}{0}]\)'s and \(q[\binom{0}{1}]\)'s. We give new exact values: forb\((m,F_{0,4})=\lfloor \frac{5m}{2}\rfloor +2\), forb\((m,F_{1,4})=\lfloor \frac{11m}{4}\rfloor + 1\), forb\((m,F_{1,5})=\lfloor \frac{15m}{4}\rfloor +1\), forb\((m,F_{2,4})=\lfloor \frac{10m}{3}-\frac{4}{3}\rfloor\) and forb\((m,F_{2,5})=4m\) (For forb\((m,F_{1,4})\), forb\((m,F_{1,5})\) we obtain equality only for certain classes modulo 4). In addition we provide a surprising construction which shows \({\text{forb}}(m,F_{pq})\geq (\frac{p+q}{2}+O(1))m\).