Salve, ricevo ed inoltro p.c.. Cordialmente, m.gianfelice ----------------------------------------------------------------------- Michele Gianfelice, PhD Dipartimento di Matematica e Informatica Università della Calabria Telephone : +39 0984 496412 Campus di Arcavacata Fax : +39 0984 496410 Ponte P. Bucci - cubo 30B email: gianfelice@mat.unical.it I-87036 Arcavacata di Rende (CS) www.mat.unical.it/~gianfelice/ ----------------------------------------------------------------------- ---------- Forwarded message ---------- Date: Thu, 23 Sep 2021 20:43:34 +0200 From: One World Probability <ow.probability@gmail.com> To: owps@lists.bath.ac.uk Subject: [owps] OWPS, October 7th: P. Diaconis and L. Miclo on "THE random graph" Dear probabilists, We are pleased to inform you that the OWPS will resume on October 7th, from 14:00 to 15:45 UTC. Persi Diaconis and Laurent Miclo will talk about THE random graph and random walk on it. Titles, abstracts and the Zoom link are below the signature, and can be found on the website https://www.owprobability.org/one-world-probability-seminar. We also inform you that, in accordance with the wishes expressed in the pooling, sessions will take place every other week (i.e. ~2 per month). Each session will consist of two talks of 45 minutes each. These two talks will be thematically unified. Please feel free to circulate this email. Probabilistically yours, Bastien Mallein and Sébastien Martineau -------- Persi Diaconis -- Probability theory for THE random graph Pick two Erdös-Renyi (n,1/2) graphs uniformly at random. What's the chance they are the same (isomorphic)? Small. How small? Well, at most n!/ 2^(n choose 2). When n= 100, that's less than 10^-1300. OK, now let n=infinity. The chance that the two graphs are isomorphic is one (!). This is THE random graph (the Rado graph R). I will review its many non-random models and many strange properties. ? It is a natural limit of the set of all finite graphs (a first order property is true for almost all finite graphs if and only if it holds with probability one in R) and this discontinuity is surprising. In joint work with with Sourav Chatterjee we tried to find finite manifestations: For finite n, the largest isomorphic induced subgraph of a pair has size 4log (n) -2loglog(n)-2log(4/e) +1 (within 1, all logs base 2 in probability when n is large). This matches data amazingly well (e.g. for n more than 30) and illuminates problems in constraint satisfaction. Laurent Mico -- A random walk on THE random graph R Let q(j) be a probability on N={0,1,2,...}. Let R be a model of THE random graph. A Markov chain on N starts at i and moves to one of its neighbor j in R with probability proportional to q(j). This Markov chain has a stationary distribution and we inquire about rates of convergence. Since each vertex is connected to half of the others and the diameter of R is 2, it seems likely that convergence is fast. In some models we show that log* (i) steps are necessary and sufficient for convergence. The proof uses a novel variant of Hardy's inequalities for trees. This is joint work with Sourav Chatterjee and Persi Diaconis. Zoom-link: https://us02web.zoom.us/j/81721277245?pwd=VjhadGFZcTVZamsvRkhZUExVbHAyZz09 Meeting ID 817 2127 7245 Passcode: 759491 If you are having trouble with zoom, or if the capacity of the zoom room gets exceeded, you can also access to the Youtube live stream at the channel of the seminar: https://www.youtube.com/channel/UCiLiEQGTp6bZEhuHDM-WNWQ