BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/441
DTSTAMP:20230914T125924Z
SUMMARY:Szemeredi's Regularity Lemma and It's Applications
DESCRIPTION:Speaker: Rakesh Venkat\n\nAbstract: \nAbstract: Szemeredi's Reg
ularity lemma is key result in extremal graph theory\, that roughly states
the following: For any $\\epsilon>0$\, the vertex set of a graph $G=(V\,E
)$ can be partitioned into $k=C(\\epsilon)$ (i.e. a constant number of) pa
rts $V_1\, ... \, V_k$ of equal size\, such that the induced subgraph on m
ost pairs $(V_i\, V_j)$ is '$\\epsilon$-close' to being a regular bipartit
e graph. Besides many combinatorial applications\, it can also be used to
get polynomial time approximation schemes for various problems on dense gr
aphs. We will look at a proof of a weakened version of the Regularity Lemm
a\, andÂ discuss a couple of it's applications.\n
URL:https://www.tcs.tifr.res.in/web/events/441
DTSTART;TZID=Asia/Kolkata:20140110T161500
DTEND;TZID=Asia/Kolkata:20140110T171500
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR