# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 19.12.2019 at 12:30 in S6, there is the following noon lecture:

# Forcing quasi-randomness in permutations

## Jan Volec

## Masaryk University

## Abstract

Quasi-random properties of combinatorial structures such as graphs, hypergraphs or permutations are deterministic conditions that forces a given (deterministic) structure to have "random-like" behavior. In the late 1980s, seminal papers of Rödl, Thomason, and Chung, Graham and Wilson initiated a systematic study of properties that forces a large graph to be quasi-random. For example, if a graph G with density p has the correct subgraph densities of all 4-vertex graphs, i.e., the same as a typical random graph G(n,p), then G has the correct subgraph density of any fixed graph.

In 2012, an analogous result was proven for permutations by Kráµ and Pikhurko, who showed that if P is a large permutation where every 4-point permutation has packing density about 1/24, then P is quasi-random (i.e., any fixed k-point permutation has packing density about 1/k! ). It was known before that assuming only the six packing densities of 3-point permutations being about 1/6 does not force P to be quasi-random. In their proof, Kráµ and Pikhurko have used all the 24 packing densities so it was natural to ask how much this list can be reduced. In this talk, we present a set X of eight 4-point permutations such that if the sum of the pattern densities of elements from X in a large permutation P is about |X|/24 , then P is quasi-random. Moreover, we completely characterize all the subsets of S_4 that has this property; it turned out that there are exactly 10 such subsets.

This is joint work with T. Chan, D. Kráµ, Y. Pehova, J. Noel and M. Sharifzadeh.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page