BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CMSA - ECPv6.16.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://cmsa.fas.harvard.edu
X-WR-CALDESC:Events for CMSA
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20210314T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20211107T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20220313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20221106T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20230312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20220322T093000
DTEND;TZID=America/New_York:20220322T103000
DTSTAMP:20260727T174137
CREATED:20240214T065544Z
LAST-MODIFIED:20240304T085053Z
UID:10002552-1647941400-1647945000@cmsa.fas.harvard.edu
SUMMARY:Flip processes
DESCRIPTION:Abstract: We introduce a class of random graph processes\, which we call \emph{flip processes}. Each such process is given by a \emph{rule} which is just a function $\mathcal{R}:\mathcal{H}_k\rightarrow \mathcal{H}_k$ from all labelled $k$-vertex graphs into itself ($k$ is fixed). The process starts with a given $n$-vertex graph $G_0$. In each step\, the graph $G_i$ is obtained by sampling $k$ random vertices $v_1\,\ldots\,v_k$ of $G_{i-1}$ and replacing the induced graph $F:=G_{i-1}[v_1\,\ldots\,v_k]$ by  $\mathcal{R}(F)$. This class contains several previously studied processes including the Erd\H{o}s–R\’enyi random graph process and the triangle removal process. \nGiven a flip process with a rule $\mathcal{R}$\, we construct time-indexed trajectories $\Phi:\Gra\times [0\,\infty)\rightarrow\Gra$ in the space of graphons. We prove that for any $T > 0$ starting with a large finite graph $G_0$ which is close to a graphon $W_0$ in the cut norm\, with high probability the flip process will stay in a thin sausage around the trajectory $(\Phi(W_0\,t))_{t=0}^T$ (after rescaling the time by the square of the order of the graph). \nThese graphon trajectories are then studied from the perspective of dynamical systems. Among others\, we study continuity properties of these trajectories with respect to time and the initial graphon\, existence and stability of fixed points and speed of convergence (whenever the infinite time limit exists). We give an example of a flip process with a periodic trajectory. This is joint work with Frederik Garbe\, Matas \v Sileikis and Fiona Skerman (arXiv:2201.12272). \nWe also study several specific families flip processes. This is joint work with Pedro Ara\’ujo\, Eng Keat Hng and Matas \v{S}ileikis (in preparation).\nA brief introduction to the necessary bits of the theory of graph limits will be given in the talk.
URL:https://cmsa.fas.harvard.edu/event/3-22-2022-combinatorics-physics-and-probability-seminar/
CATEGORIES:Combinatorics Physics and Probability
ATTACH;FMTTYPE=image/png:https://cmsa.fas.harvard.edu/media/CMSA-Combinatorics-Physics-and-Probability-Seminar-3.15.2022-1-1.png
END:VEVENT
END:VCALENDAR