BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computational Optimisation Group - ECPv6.15.11//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computational Optimisation Group
X-ORIGINAL-URL:https://optimisation.doc.ic.ac.uk
X-WR-CALDESC:Events for Computational Optimisation Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20191128T140000
DTEND;TZID=UTC:20191128T153000
DTSTAMP:20260418T101913
CREATED:20191025T170003Z
LAST-MODIFIED:20191025T170134Z
UID:1418-1574949600-1574955000@optimisation.doc.ic.ac.uk
SUMMARY:Seminar with Prof. Greg Sorkin: Extremal Cuts and Isoperimetry in Random Cubic Graphs
DESCRIPTION:The minimum bisection width of random cubic graphs is of interest because it is one of the simplest questions imaginable in extremal combinatorics\, and also because the minimum bisection of (general) cubic graphs plays a role in the construction of efficient exponential-time algorithms\, and it seems likely that random cubic graphs are extremal. \nIt is known that a random cubic graph has a minimum bisection of size at most 1/6 times its order (indeed this is known for all cubic graphs)\, and we reduce this upper bound to below 1/7 (to 0.13993) by analyzing an algorithm with a couple of surprising features. We increase the corresponding lower bound on minimum bisection using the Hamilton cycle model of a random cubic graph. We use the same Hamilton cycle approach to decrease the upper bound on maximum cut. We will discuss some related conjectures.
URL:https://optimisation.doc.ic.ac.uk/event/seminar-with-prof-greg-sorkin-extremal-cuts-and-isoperimetry-in-random-cubic-graphs/
LOCATION:Huxley 217
END:VEVENT
END:VCALENDAR