- Series
- Graph Theory Seminar
- Time
- Friday, September 13, 2019 - 11:00am for 1 hour (actually 50 minutes)
- Location
- Skiles 249
- Speaker
- Dan Kral – Masaryk University and University of Warwick – http://www.ucw.cz/~kral/index.html.en
- Organizer
- Xingxing Yu
A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. For example, it is well-known that a graph G with edge-density p is quasirandom if and only if the density of C_4 in G is p^4+o(p^4); this property is known to equivalent to several other properties that hold for truly random graphs. A similar phenomenon was established for permutations: a permutation is quasirandom if and only if the density of every 4-point pattern (subpermutation) is 1/4!+o(1). We strengthen this result by showing that a permutation is quasirandom if and only if the sum of the densities of eight specific 4-point patterns is 1/3+o(1). More generally, we classify all sets of 4-point patterns having such property.
The talk is based on joint work with Timothy F. N. Chan, Jonathan A. Noel, Yanitsa Pehova, Maryam Sharifzadeh and Jan Volec.