Davenport-Schinzel theory of matrices (Q1195475)

A configuration \(C=(c_{ij})\) \((1\leq i\leq u,\;1\leq j\leq v)\) is a partial matrix with 1's and blanks at the entries. We say that a matrix \(M=(m_{ij})\) does contain the configuration \(C\) if there are rows \(i_ 1<\cdots<i_ u\) and columns \(j_ 1<\dots<j_ v\) such that \(m_{i_ \alpha j_ \beta}=1\) whenever \(c_{\alpha\beta}=1\). Let \(f(n,m,C)\) denote the maximum number of 1's in an \(n\times m\) matrix \(M\) not containing \(C\). In the paper the problem of determining the order of \(f(m,m,C)\) for several \(C\)'s is considered. Among other results it is proved that \(f\left(n,n,{1\;1\;\choose\;1\;1}\right)=\theta(\alpha(n)n)\), where \(\alpha(n)\) is the inverse of the Ackermann function.