BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20160313T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20161106T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20220930T150631Z
UID:c0d0ac38-7b1b-4f44-9d70-38e53785ecf4
DTSTART;TZID=America/New_York:20160823T160000
DTEND;TZID=America/New_York:20160823T170000
CREATED:20160816T095108
DESCRIPTION:It is a truth universally acknowledged\, that random objects ar
e asymmetric. It was shown by Wright (1971) that for p slightly larger tha
n logn / n a random G(n\,p) graph has\, whp\, a trivial automorphism group
. This bound is tight\, since a graph of slightly smaller density is likel
y to have isolated vertices. Our work concerns sparser graphs\, where the
average degree still goes to infinity but p is below Wright's threshold. W
e show that in this range\, whp all of G's automorphisms are essentially t
rivial. More concretely\, it holds almost surely that G's 2-core (i.e.\, t
he maximal subgraph of G with minimal degree at least 2) has only the triv
ial automorphism. Our theorem yields some interesting insights on the grap
h reconstruction conjecture\, as well as a new algorithm for random graph
canonical labeling.\n\nThis is a joint work with Nati Linial.
LAST-MODIFIED:20160816T110308
LOCATION:32-G575
SUMMARY:On the Rigidity of Sparse Random Graphs
URL:https://calendar.csail.mit.edu/events/175221
END:VEVENT
END:VCALENDAR