Colloquium by Yanitsa Pehova (University of Warwick): Characterisation of quasirandom permutations by a pattern sum
We say that a sequence {π_i} of permutations is quasirandom if, for each k>1 and each σ∈S_k, the probability that a uniformly chosen k-set of entries of π_i induces σ tends to 1/k! as i tends to infinity. It is known that a much weaker condition already forces π_i to be quasirandom; namely, if the above property holds for all σ∈S4. We further weaken this condition by exhibiting sets S⊆S4, such that if randomly chosen four entries of π_i induce an element of S with probability tending to |S|/24, then {π_i} is quasirandom. Moreover, we are able to completely characterise the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec.
Time & Location
Feb 03, 2020 | 04:00 PM s.t.
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)