BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CMSA - ECPv6.16.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CMSA
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:20220308T090000
DTEND;TZID=America/New_York:20220308T100000
DTSTAMP:20260727T171444
CREATED:20240214T064241Z
LAST-MODIFIED:20240304T090552Z
UID:10002550-1646730000-1646733600@cmsa.fas.harvard.edu
SUMMARY:Greedy maximal independent sets via local limits
DESCRIPTION:Abstract: The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics\, probability\, computer science\, and chemistry. The algorithm builds a maximal independent set by inspecting the graph’s vertices one at a time according to a random order\, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge. \nIn this talk\, I will present a simple yet general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs\, involving a valuable notion of local convergence. I will demonstrate the applicability of this framework by giving short and straightforward proofs for results on previously studied families of graphs\, such as paths and various random graphs\, and by providing new results for other models such as random trees. \nIf time allows\, I will discuss a more delicate (and combinatorial) result\, according to which\, in expectation\, the cardinality of a random greedy independent set in the path is no larger than that in any other tree of the same order. \nThe talk is based on joint work with Michael Krivelevich\, Tamás Mészáros and Clara Shikhelman.
URL:https://cmsa.fas.harvard.edu/event/3-8-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.08.2022.png
END:VEVENT
END:VCALENDAR