This talk will survey the extremal theory of pattern-avoiding 0-1 matrices and some of their applications in geometry and algorithms. If P is a 0-1 matrix, Ex(P,n) is the maximum number of 1s in an n x n 0-1 matrix that does not contain any submatrix that dominates P. Every 0-1 pattern P can be regarded as the incidence matrix of a bipartite graph, in which the two sides of the bipartition are ordered. Thus, this definition can be seen as a generalization of the Turan extremal function (for subgraph avoidance).

Pattern-avoiding 0-1 matrices have been studied since the late 1980s, and yet the precise relationship between 0-1 matrices and Turan theory is still poorly understood. For many years the foremost open problem has been to characterize the extremal functions of acyclic patterns (those whose graphs correspond to forests). In 2005 Pach and Tardos conjectured that Ex(P,n) = O(n polylog(n)) for any acyclic P. We give a simple refutation of the Pach-Tardos conjecture by giving a class of acyclic patterns for which Ex(P,n) > n 2^{sqrt{log n}}.

Joint work with Gábor Tardos. Paper available at: https://arxiv.org/abs/2407.02638.