Tournament quasirandomness from local counting

DOI10.1007/S00493-020-4371-YMaRDI QIDQ2036620zbMATH OpenOpenAlexFDO

Authors Eoin Long, Asaf Shapira, Matija Bucić, Benny Sudakov

Publication date 29 June 2021

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

forcingtournamentquasi-randomsubtournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: A well-known theorem of Chung and Graham states that if $hgeq4$ then a tournament $T$ is quasirandom if and only if $T$ contains each $h$-vertex tournament the "correct number" of times as a subtournament. In this paper we investigate the relationship between quasirandomness of $T$ and the count of a single $h$-vertex tournament $H$ in $T$. We consider two types of counts, the global one and the local one. We first observe that if $T$ has the correct global count of $H$ and $hgeq7$ then quasirandomness of $T$ is only forced if $H$ is transitive. The next natural question when studying quasirandom objects asks whether possessing the correct local counts of $H$ is enough to force quasirandomness of $T$. A tournament $H$ is said to be locally forcing if it has this property. Variants of the local forcing problem have been studied before in both the graph and hypergraph settings. Perhaps the closest analogue of our problem was considered by Simonovits and S'os who looked at whether having "correct counts" of a fixed graph $H$ as an induced subgraph of $G$ implies $G$ must be quasirandom, in an appropriate sense. They proved that this is indeed the case when $H$ is regular and conjectured that it holds for all $H$ (except the path on 3 vertices). Contrary to the Simonovits-S'os conjecture, in the tournament setting we prove that a constant proportion of all tournaments are not locally forcing. In fact, any locally forcing tournament must itself be strongly quasirandom. On the other hand, unlike the global forcing case, we construct infinite families of non-transitive locally forcing tournaments.

Recommendations

• No additional tournaments are quasirandom-forcing
• On the density of transitive tournaments
• Quasi-carousel tournaments
• Quasi-randomness and the distribution of copies of a fixed graph
• Quasi-random tournaments

Cites work

• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• A note on even cycles and quasirandom tournaments
• Algorithms in real algebraic geometry
• Algorithms with large domination ratio
• Analysis of Boolean Functions
• Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
• Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs
• Hereditary quasirandom properties of hypergraphs
• Hereditary quasirandomness without regularity
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On extremal problems of graphs and generalized graphs
• On the density of transitive tournaments
• On the maximum cardinality of a consistent set of arcs in a random tournament
• On the maximum density of fixed strongly connected subtournaments
• On the maximum number of Hamiltonian paths in tournaments
• Optimal ranking of tournaments
• Pseudo-random graphs
• Quasi-Random Set Systems
• Quasi-random graphs
• Quasi-random oriented graphs
• Quasi-random tournaments
• Quasirandom Groups
• Quasirandom permutations
• Quasirandom permutations are characterized by 4-point densities
• Regularity Lemma for k-uniform hypergraphs
• Testing subgraphs in directed graphs
• The counting lemma for regular k‐uniform hypergraphs
• The probabilistic method
• Weak quasi-randomness for uniform hypergraphs

Cited in

(12)

• On the density of transitive tournaments
• No additional tournaments are quasirandom-forcing
• A note on even cycles and quasirandom tournaments
• Characterization of quasirandom permutations by a pattern sum
• Quasirandom-Forcing Orientations of Cycles
• On explicit random-like tournaments
• Cycles of a given length in tournaments
• Forcing generalised quasirandom graphs efficiently
• Lower bound on the size of a quasirandom forcing set of permutations
• Forcing quasirandomness with triangles
• Quasirandom Latin squares
• Quasi-carousel tournaments

This page was built for publication: Tournament quasirandomness from local counting

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