A TOURNAMENT APPROACH TO PATTERN AVOIDING MATRICES

We consider the following Turan-type problem: given a fixed tournament H, what is the least integer t = t(n, H) so that adding t edges to any n-vertex tournament, results in a digraph containing a copy of H. Similarly, what is the least integer t = t(T-n, H) so that adding t edges to the n-vertex transitive tournament, results in a digraph containing a copy of H. Besides proving several results on these problems, our main contributions are the following: Pach and Tardos conjectured that if M is an acyclic 0/1 matrix, then any n x n matrix with n(log n)(O(1)) entries equal to 1 contains the pattern M. We show that this conjecture is equivalent to the assertion that t(T-n, H) = n(log n)(O(1)) if and only if H belongs to a certain (natural) family of tournaments. We propose an approach for determining if t(n, H) = n(log n)(O(1)). This approach combines expansion in sparse graphs, together with certain structural characterizations of H-free tournaments. Our result opens the door for using structural graph theoretic tools in order to settle the Pach-Tardos conjecture.