Séminaire Stéphanois de Mathématiques Accessibles

Quasi-random words and limits of word sequences

by Marcos KIWI ((Univ. de Chile))

Salle A 24 (ICJ STE Campus Métare)

Salle A 24

ICJ STE Campus Métare


Quasi-random structures, roughly speaking, are deterministic objects which share many characteristic properties of their random counterparts.Formalizing this concept has turned out to be tremendously fruitful. Over the last two decades it has been recognized that quasi-randomness and limits of discrete structures are two related subjects.  Being interesting on their own right, limit theories have also unveiled many connections between various branches of mathematics and theoretical computer science.

The first quasi-random structures were identified by Thomason (1987) and Chung, Graham and Wilson (1989). The theory of limit objects was launched by the work of Lovaasz and Szegedy (2006).

In this self-contained talk we expound on the theory of quasi-random structures and limit objects by focusing on simple yet fundamental discrete objects; words and convergent word sequences. Surprisingly, neither had been explicitly investigated in the rich literature of quasi-randomness and limits of discrete structures.

Join work with Hiep Han (U. de Santiago de Chile) and Matias Pavez Signé (U. de Chile)

Keywords: Quasi-randomness, limits of discrete structures, property testing.

Prérequis: Some familiarity with discrete probabilities and basic notions of calculus and measure theory.