Tournament quasirandomness from local counting (Q2036620)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tournament quasirandomness from local counting |
scientific article |
Statements
Tournament quasirandomness from local counting (English)
0 references
29 June 2021
0 references
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)
0 references
tournament
0 references
quasi-random
0 references
forcing
0 references
subtournament
0 references
0 references