Аннотация:
We prove that for every fixed $k$, the number of occurrences of the transitive tournament $Tr_k$ of order $k$ in a tournament $T_n$ on $n$ vertices is asymptotically minimized when $T_n$ is random. In the opposite direction, we show that any sequence of tournaments $\{T_n\}$ achieving this minimum for any fixed $k\ge 4$ is necessarily quasi-random. We present several other characterizations of quasi-random tournaments nicely complementing previously known results and relatively easily following from our proof techniques.
Leonardo Nagami Coregliano: Contract grant sponsor: Fundacão de Amparo à Pesquisa do Estado de São Paulo (FAPESP); Contract grant numbers: 2013/23720-9 and 2014/15134-5. Work done while visiting the University of Chicago.
Alexander A. Razborov: Contract grant sponsor: Russian Foundation for Basic Research Part of the work done while the author was at Steklov Mathematical Institute and Toyota Technological Institute at Chicago.
Поступила в редакцию: 10.02.2015 Исправленный вариант: 11.03.2016
Реферативные базы данных:
Тип публикации:
Статья
Язык публикации: английский
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/jgt1
Эта публикация цитируется в следующих 19 статьяx:
Raphael Yuster, “Finding and counting small tournaments in large tournaments”, Theoretical Computer Science, 1024 (2025), 114911
FREDERIK GARBE, DANIEL KRÁL', ALEXANDRU MALEKSHAHIAN, RAUL PENAGUIAO, “The dimension of the feasible region of pattern densities”, Math. Proc. Camb. Phil. Soc., 2025, 1
Andrzej Grzesik, Daniel Král', Oleg Pikhurko, “Forcing generalised quasirandom graphs efficiently”, Combinator. Probab. Comp., 33:1 (2024), 16
Victor Falgas‐Ravry, Oleg Pikhurko, Emil Vaughan, Jan Volec, “The codegree threshold of K4-$K_4^{-}$”, Journal of London Math Soc, 107:5 (2023), 1660
Andrzej Grzesik, Daniel Il'kovič, Bartłomiej Kielak, Daniel Král', “Quasirandom-Forcing Orientations of Cycles”, SIAM J. Discrete Math., 37:4 (2023), 2689
Andrzej Grzesik, Daniel Král', László M. Lovász, Jan Volec, “Cycles of a given length in tournaments”, Journal of Combinatorial Theory, Series B, 158 (2023), 117
Leonardo N. Coregliano, Alexander A. Razborov, “Natural quasirandomness properties”, Random Structures Algorithms, 63:3 (2023), 624–688
Andrzej Grzesik, Daniel Kráľ, Oleg Pikhurko, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, 2023, 503
Robert Hancock, Adam Kabela, Daniel Král', Taísa Martins, Roberto Parente, Fiona Skerman, Jan Volec, “No additional tournaments are quasirandom-forcing”, European Journal of Combinatorics, 108 (2023), 103632
Martin Kurečka, “Lower bound on the size of a quasirandom forcing set of permutations”, Combinator. Probab. Comp., 31:2 (2022), 304
Jacob W. Cooper, Daniel Král', Ander Lamaison, Samuel Mohr, “Quasirandom Latin squares”, Random Struct Algorithms, 61:2 (2022), 298
Matija Bucić, Eoin Long, Asaf Shapira, Benny Sudakov, “Tournament Quasirandomness from Local Counting”, Combinatorica, 41:2 (2021), 175
Timothy F. N. Chan, Daniel Král', Jonathan A. Noel, Yanitsa Pehova, Maryam Sharifzadeh, Jan Volec, “Characterization of quasirandom permutations by a pattern sum”, Random Struct Algorithms, 57:4 (2020), 920
DANIEL KRÁL', BERNARD LIDICKÝ, TAÍSA L. MARTINS, YANITSA PEHOVA, “Decomposing Graphs into Edges and Triangles”, Combinator. Probab. Comp., 28:3 (2019), 465
Обратная связь: