No additional tournaments are quasirandom-forcing

DOI10.1016/J.EJC.2022.103632zbMATH Open1504.05106arXiv1912.04243OpenAlexW2991990030MaRDI QIDQ2107498FDOQ2107498

Authors: Robert Hancock, Adam Kabela, Daniel Král', Fiona Skerman, Jan Volec, Taísa L. Martins, R. F. Parente 

Publication date: 1 December 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: A tournament H is quasirandom-forcing if the following holds for every sequence (G_n) of tournaments of growing orders: if the density of H in G_n converges to the expected density of H in a random tournament, then (G_n) is quasirandom. Every transitive tournament with at least 4 vertices is quasirandom-forcing, and Coregliano et al. [Electron. J. Combin. 26 (2019), P1.44] showed that there is also a non-transitive 5-vertex tournament with the property. We show that no additional tournament has this property. This extends the result of Bucic et al. [Combinatorica 41 (2021), 175-208] that the non-transitive tournaments with seven or more vertices do not have this property.

Full work available at URL: https://arxiv.org/abs/1912.04243

Recommendations

• Quasi-random tournaments
• On explicit random-like tournaments
• Tournament quasirandomness from local counting
• Equations of tournaments are not finitely based
• scientific article; zbMATH DE number 7300409
• scientific article; zbMATH DE number 3916313
• A note on even cycles and quasirandom tournaments
• Publication:3496355
• Nearly-acyclically pushable tournaments

zbMATH Keywords

random tournamentnon-transitive 5-vertex tournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Title not available (Why is that?)
• Graph limits and exchangeable random graphs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Regularity Lemma for k-uniform hypergraphs
• The counting lemma for regular k‐uniform hypergraphs
• Title not available (Why is that?)
• Quasi-random graphs
• On universality of graphs with uniformly distributed edges
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quasi-random hypergraphs
• Title not available (Why is that?)
• Quasirandom Groups
• Asymmetric graphs
• A Constructive Solution to a Tournament Problem
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Hypergraphs, quasi-randomness, and conditions for regularity
• Quasirandom permutations are characterized by 4-point densities
• Quasi-Random Set Systems
• An approximate version of Sidorenko's conjecture
• The Maximum Number of Strongly Connected Subtournaments^*
• Quasirandom permutations
• Quasi-random tournaments
• Bipartite subgraphs and quasi-randomness
• On the Density of Transitive Tournaments
• Quasi-random subsets of \(\mathbb{Z}_ n\)
• Pseudo-random hypergraphs
• On the maximum density of fixed strongly connected subtournaments
• Characterization of quasirandom permutations by a pattern sum
• Tournament quasirandomness from local counting
• No additional tournaments are quasirandom-forcing
• Decomposition of tournament limits
• Impartial digraphs

Cited In (5)

• No additional tournaments are quasirandom-forcing
• Quasirandom-Forcing Orientations of Cycles
• Forcing generalised quasirandom graphs efficiently
• Cycles of a given length in tournaments
• Lower bound on the size of a quasirandom forcing set of permutations

Uses Software

• SageMath

This page was built for publication: No additional tournaments are quasirandom-forcing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2107498)