Gabor Tardos 

Forbidden acyclic patterns in 0-1 matrices

A zero-one matrix M is said to contain another zero-one matrix A if we can
delete some rows and columns of M and replace some 1-entries with 0-entries
such that the resulting matrix is A. The extremal function of A, denoted
ex(n, A), is the maximum number of 1-entries that an nXn zero-one matrix can
have without containing A. The systematic study of this function for various
patterns A goes back to the work of Furedi and Hajnal from 1992.
The field has many connections to other areas such as classical Turan
type extremal graph theory and Davenport-Schinzel theory and has many
applications in mathematics and theoretical computer science.
The problem has been particularly extensively studied for so-called acyclic
matrices. Furedi and Hajnal conjectured an O(n log n) bound for them,
while Pach and Tardos conjectured a weaker n polylog n bound.
Pettie refuted the stronger conjecture with an acyclic pattern whose extremal
function he showed to be Omega(n log n log log n).

In a recent joint work with Seth Pettie we found the extremal function
ex(n, A_k) asymptotically for certain simple 2Xk acyclic patterns to be

Theta(n(log n/log log n)^(k-2)) for k>3.
This shows that the Pach-Tardos conjecture is tight if true.
The conjecture itself is still wide open.