BEGIN:VCALENDAR
VERSION:2.0
PRODID:-// - ECPv5.3.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://aarms.math.ca
X-WR-CALDESC:Events for 
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20230329T153000
DTEND;TZID=UTC:20230329T163000
DTSTAMP:20260609T075722
CREATED:20230325T113759Z
LAST-MODIFIED:20230325T113833Z
UID:7190-1680103800-1680107400@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar: Calum MacRury\, University of Toronto
DESCRIPTION:Approximation Schemes for Resource Minimization for Fire Containment\nThe semi-random graph process is an example of an adaptive process for constructing a graph in which random edges are added step by step.  It is adaptive in that there is an online algorithm which has partial control over which random edges are added. Through intelligent decision-making\, the objective of the algorithm is to force the graph to satisfy a fixed graph property with high probability in as few rounds as possible. We first provide upper and lower bounds on the performance of an optimal algorithm when the property corresponds to being Hamiltonian or to containing a perfect matching. This part of the talk is based on joint works with Pawel Pralat and Jane Gao.Afterwards\, we introduce a formal definition of an adaptive random graph process which generalizes both the semi-random graph process\, as well as the Achlioptas process. In this model\, we define a condition called edge-replaceability  which we prove is sufficient for a property to have a sharp threshold. Intuitively\, a property has a sharp threshold if the optimal algorithm’s “success probability” transitions from almost $0$ to almost $1$ in a negligible number of steps.  We apply our result to the semi-random graph process to show that the properties of being Hamiltonian  and of containing a perfect matching each have a sharp threshold. This part of the talk is based on a joint work with Erlang Surya.
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-calum-macrury-university-of-toronto/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="jeannette%20Janssen":MAILTO:jeannette.janssen@dal.ca
END:VEVENT
END:VCALENDAR