Quasirandom graphs, permutations and Latin squares

Abstract: A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is. A closely related notion is the notion of common graphs, which are graphs whose number of monochromatic copies is minimized by the (quasi)random coloring of a host complete graph.

We will discuss quasirandom properties of permutations and Latin squares, and present several recent results obtained using analytic tools of the theory of combinatorial limits. We will also present some recent results on common and locally common graphs, in particular, we show that there exists common connected graphs with arbitrary large chromatic number, whose existence was an open problem for more than 20 years.

The talk is based on results obtained with different groups of collaborators, including Timothy F. N. Chan, Jacob W. Cooper, Robert Hancock, Matjaž Krnc, Ander Lamaison, Samuel Mohr, Jonathan A. Noel, Sergey Norin, Yanitsa Pehova, Oleg Pikhurko, Maryam Sharifzadeh, Jan Volec and Fan Wei.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).