Oliver Club

Persi DiaconisStanford University
The (one and only) random network

Thursday, March 11, 2021 - 4:00pm

Imagine 100 people. Form random interconnections by flipping a fair coin for each pair of people. If the coin comes up heads, they are connected. If tails not. If you 'do it again' forming a fresh network, what's the chance that 'it's the same?' It's infinitesimally small. BUT if you do the same thing with an infinite number of people, the two networks will be the same (almost surely). This strange, unique object is THE random network. It has amazing properties, so strange that they wonder if it really exists. Makes me wonder about infinity. Like it or not, it's useful (I'll explain how). The logician Maryanthe Milliarias and I have used it to show that some 'difficult to describe' objects really are difficult, because they contain The random graph and, after all, there is no succinct description of random things. I'll try to explain all this 'in English'.