Tournament quasirandomness from local counting

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

Abstract: A well-known theorem of Chung and Graham states that if

h g e q 4

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

h g e q 7

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.

Review text

Editorial remark: Accidentally, this article has been issued twice for reviewing. Therefore, we display both reviews, by adding the second one to the originally published review: The paper under review studies quasi-randomness of tournaments. A combinatorial structure is, informally, quasi-random if it resembles a typical random such structure. In the tournament context, \textit{F. R. K. Chung} and \textit{R. L. Graham} [J. Graph Theory 15, No. 2, 173--198 (1991; Zbl 0728.05025)] have shown that any of several properties is equivalent to their formal definition of quasi-randomness. One of these properties is that the number of copies of each fixed tournament \(H\) (with \(h\) vertices) in the tournament is asymptotically the number which would be expected if the tournament was genuinely random. \par The initial results in this paper deal with the question of when having asymptotically the right number of copies of a single tournament forces quasi-randomness. It has been known for some time that transitive tournaments have this property, as does a certain 5-vertex tournament which is not transitive. The first result is that there are no other such tournaments with at least 7 vertices. Subsequent work of \textit{R. Hancock} et al. [``No additional tournaments are quasirandom-forcing, Preprint, \url{arXiv:1912.04243}] shows also that there are no such tournaments with 5 and 6 vertices. \par The previous paragraph deals with a global count forcing quasi-randomness: one can also consider a local notion where if, for every subset \(U\) of the vertices of the tournament, we have that the number of copies of \(H\) is the expected number under genuine randomness plus or minus a term which is \(o(n^{h})\) where \(n\) is the number of vertices in the host tournament. The authors demonstrate a number of results on tournaments which are locally forcing quasi-randomness in this sense. Firstly, they show that \(H\) must itself have good quasi-random properties. However, they next show the surprising result that the random tournament is not locally forcing with positive probability. Nevertheless, they succeed in showing that for all large enough \(h\) there are non-transitive \(h\)-vertex locally forcing tournaments. \par A key idea in proofs is a link between local forcing and certain graph polynomials. Reviewer: David B. Penman (Colchester) A well-known theorem of \textit{F. R. K. Chung} and \textit{R. L. Graham} [J. Graph Theory 15, No. 2, 173--198 (1991; Zbl 0728.05025)] states that if \(h\ge 4\) 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 work the relationship between quasirandomness of \(T\) and the count of a single \(h\)-vertex tournament \(H\) in \(T\) are investigated. Two types of counts -- the global one and the local one are considered. It is observed that if \(T\) has the correct global count of \(H\) and \(h\ge 7\) the 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. Next, variants of the local forcing problem have been studied before in both the graph and hipergraph settings. Perhaps the closest analogue of this problem was considered by \textit{M. Simonovits} and \textit{V. T. Sós} [Combinatorica 17, No. 4, 577--596 (1997; Zbl 0906.05066)] 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). It is proved, that this is the case when \(H\) is regular and it is conjectured that it holds for all \(H\) (except the path on \(3\)). Contrary to the Simonovits-Sós conjecture, in the tournament settings, the authors have proved 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, infinite families of non-transitive locally forcing tournaments are constructed. Reviewer: Mirko Lepović (Kragujevac)

Recommendations

Cites work

Cited in

(16)

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)