Event

Alg/Comb Seminar: Frederik Garbe, Graph Processes Modelled as Dynamical Systems on Banach Spaces

Ort: Max-Planck-Institut für Mathematik in den Naturwissenschaften, E1 05 (Leibniz-Saal)

Speaker: Frederik Garbe

Title: Graph Processes Modelled as Dynamical Systems on Banach Spaces

Abstract: We consider the following broad class of graph processes called flip processes. Given a large graph $G$, we sample an ordered $k$-tuple of vertices uniformly at random and replace the induced subgraph with another graph on $k$ vertices according to a predetermined -- possibly randomized -- rule. This rule can be described by a transition matrix on the set of all labelled graphs on $k$ vertices, where each entry specifies the probability of replacing a particular sampled subgraph with a particular replacement graph.Our aim is to model the evolution of such processes.

In the early 2000s, Borgs, Chayes, Lovász, Sós, Szegedy, and Vesztergombi initiated a limit theory for dense graphs, leading to the introduction of graphons: symmetric measurable functions $W:[0,1]^2\rightarrow[0,1]$ which, equipped with the graph-theoretically motivated cut norm, form a complete metric space.

Given a flip process rule, we construct time-indexed trajectories in the graphon space
such that the associated random graph process evolves, with high probability, close to one of these trajectories. We then study these graphon trajectories from the perspective of dynamical systems.

This is joint work with Jan Hladký, Matas Šileikis and Fiona Skerman.

No Attachment

Beginn: Dec. 11, 2025, 11 a.m.

Ende: Dec. 11, 2025, noon