BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1296
DTSTAMP:20230914T125958Z
SUMMARY:Functionality of a Random Graph is Polylogarithmic
DESCRIPTION:Speaker: Pavel Dvorak\n\nAbstract: \nThe functionality of a gra
ph defined by [Alecu et al.: Graph functionality\, JCTB2021] is a paramete
r that generalizes graph degeneracy.\nInformally\, the functionality of a
graph G is minimal k such that in any induced subgraph H of G there is a v
ertex v in H and a set S of k vertices that the adjacency of v and any ver
tex u in H is determined by adjacency of u and S.\nI'll show that random g
raph G = G(n\,p) has functionality asymptotically at least log n and at mo
st log^3 n. The upper bound is a fresh new result\, I'll be happy to discu
ss its correctness.\nThis is joint work with L. Folwarczný\, M. Opler\, P
. Pudlák\, R. Šámal\, T. Vu.\n
URL:https://www.tcs.tifr.res.in/web/events/1296
DTSTART;TZID=Asia/Kolkata:20230526T160000
DTEND;TZID=Asia/Kolkata:20230526T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR