BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We say that a sequence {π _ i } of permutations is quasirando
m if\, for each k>\;1 and each σ∈ S _ k \, the probability that a unifo
rmly 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 σ∈
S 4 . We further weaken this condition by exhibiting sets S⊆ S 4 \, such
that if randomly chosen four entries of π _ i induce an element of S w
ith probability tending to | S |/24\, then {π _ i } is quasirandom. Moreov
er\, we are able to completely characterise the sets S with this property
. In particular\, there are exactly ten such sets\, the smallest of which h
as cardinality eight. This is joint work with Timothy Chan\, Daniel Král'\,
Jon Noel\, Maryam Sharifzadeh and Jan Volec.
DTSTAMP:20200122T165400
DTSTART:20200203T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Yanitsa Pehova (University of Warwick): Characterisation of quasira
ndom permutations by a pattern sum
UID:104961400@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200203-C-Pehova.html
END:VEVENT
END:VCALENDAR