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:20200308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20201101T060000
END:STANDARD
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
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20210910T093000
DTEND;TZID=America/New_York:20210910T103000
DTSTAMP:20260712T163001
CREATED:20240213T114336Z
LAST-MODIFIED:20240304T100309Z
UID:10002512-1631266200-1631269800@cmsa.fas.harvard.edu
SUMMARY:Threshold phenomena in random graphs and hypergraphs
DESCRIPTION:Member Seminar \nSpeaker: Michael Simkin \nTitle: Threshold phenomena in random graphs and hypergraphs \nAbstract: In 1959 Paul Erdos and Alfred Renyi introduced a model of random graphs that is the cornerstone of modern probabilistic combinatorics. Now known as the “Erdos-Renyi” model of random graphs it has far-reaching applications in combinatorics\, computer science\, and other fields. \nThe model is defined as follows: Given a natural number $n$ and a parameter $p \in [0\,1]$\, let $G(n;p)$ be the distribution on graphs with $n$ vertices in which each of the $\binom{n}{2}$ possible edges is present with probability $p$\, independent of all others. Despite their apparent simplicity\, the study of Erdos-Renyi random graphs has revealed many deep and non-trivial phenomena. \nA central feature is the appearance of threshold phenomena: For all monotone properties (e.g.\, connectivity and Hamiltonicity) there is a critical probability $p_c$ such that if $p >> p_c$ then $G(n;p)$ possesses the property with high probability (i.e.\, with probability tending to 1 as $n \to \infty$) whereas if $p << p_c$ then with high probability $G(n;p)$ does not possess the property. In this talk we will focus on basic properties such as connectivity and containing a perfect matching. We will see an intriguing connection between these global properties and the local property of having no isolated vertices. We will then generalize the Erdos-Renyi model to higher dimensions where many open problems remain.
URL:https://cmsa.fas.harvard.edu/event/9-10-2021-member-seminar/
LOCATION:MA
CATEGORIES:Member Seminar
END:VEVENT
END:VCALENDAR