Abstract
We consider the following Turán-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 × 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon, J. Pach and J. Solymosi, Ramsey-type theorems with forbidden subgraphs, Combinatorica 21 (2001), 155–170.
E. Berger, K. Choromanski and M. Chudnovsky, On the Erdős–Hajnal conjecture for six-vertex tournaments, arXiv:1508.04992.
E. Berger, K. Choromanski and M. Chudnovsky, Forcing large transitive subtournaments, Journal of Combinatorial Theory, Series B 112 (2015), 1–17.
E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl, A. Scott, P. Seymour, and S. Thomassé, Tournaments and colouring, Journal of Combinatorial Theory, Series B 103 (2013), 1–20.
K. Choromanski, The strong EH-property and the Erdős–Hajnal conjecture, arXiv:1410.7049.
K. Choromanski, M. Chudnovsky and P. Seymour, Tournaments with near-linear transitive subsets, Journal of Combinatorial Theory, Series B 109 (2014), 228–249.
P. Erdős and L. Moser, On the representation of directed graphs as unions of orderings, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964), 125–132.
P. Erdős and J. Spencer, Probabilistic methods in combinatorics, Academic Press, London, New York, 1974.
P. Erdős and A. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087–1091.
Z. Füredi and P. Hajnal, Davenport-Schinzel theory of matrices, Discrete Mathematics 103 (1992), 233–251.
T. Kövari, V. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50–57.
B. Latka, Structure theorem for tournaments omitting N5, Journal of Graph Theory 42 (2003), 165–192.
F. Lazebnik, V. Ustimenko and A. Woldar, A new series of dense graphs of high girth, Bulletin of the American Mathematical Society 32 (1995), 73–79.
G. Liu, Structure theorem for U5-free tournaments, Journal of Graph Theory 78 (2015), 28–42.
A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley–Wilf conjecture, Journal of Combinatorial Theory, Series A 107 (2004), 153–160.
J. Pach and G. Tardos, Forbidden paths and cycles in ordered graphs and matrices, Israel Journal of Mathematics 155 (2006), 359–380.
S. Pettie, On nonlinear forbidden 0-1 matrices: A refutation of Füredi–Hajnal conjecture, Proceedings of the Twenty-First Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), 2010, pp. 875–885.
R. Stearns, The voting problem, American Mathematical Monthly 66 (1959), 761–763.
P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), 436–452.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported in part by ISF Grant 224/11, Marie-Curie CIG Grant 303320 and ERC Starting Grant 633509.
Rights and permissions
About this article
Cite this article
Shapira, A., Yuster, R. A tournament approach to pattern avoiding matrices. Isr. J. Math. 217, 477–505 (2017). https://doi.org/10.1007/s11856-017-1455-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-017-1455-5