Title: Forcing Quasirandomness in Permutations
| Speaker: | John Noel |
| Affiliation: | University of Victoria |
| Zoom: | Contact Steve Melczer |
Abstract:
A striking result in graph theory is that the property of a graph being quasirandom (i.e. resembling a random graph) is characterized by the number of edges and the number of 4-cycles being close to the expected number in a random graph. Král’ and Pikhurko (2013) proved an analogous result for permutations; i.e. that quasirandom permutations are characterized by the densities of all permutations of length 4. We improve on this result by showing that there is a single algebraic expression consisting of a sum of densities of 8 permutations of length 4 whose value forces quasirandomness. Moreover, we characterize all permutation expressions of this type which force quasirandomness. These results have direct implications on the problem of independence testing in non-parametric statistics. Joint work with Timothy F. N. Chan, Daniel Král’, Yanitsa Pehova, Maryam Sharifzadeh and Jan Volec.