Flip processes on dense graphs and dynamical systems

Matas Šileikis

Czech Academy of Sciences

April 28, 2022, 12:20 in S6


Consider a class of discrete time graph processes, where at each step we choose, uniformly at random, a k-tuple of vertices and transform the subgraph it induces by a predefined rule, for example "if you see a clique, remove all its edges" or "whatever you see, replace it by a random graph G(k,1/2)". We will show how to convert the question about concentration of this process (for a quadratic number of steps) to a dynamical system on a certain normed space of functions. We will consider a few examples of simple rules, and consider a rule which gives rise to a periodic trajectory. Based on work with P. Araújo, F. Garbe, J. Hladký, E. K. Hng and F. Skerman.