BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/706
DTSTAMP:20230914T125935Z
SUMMARY:Higher Order Cheeger Inequalities
DESCRIPTION:Speaker: Jenish Mehta (California Institute of Technology\nDepa
rtment of Computer Science\n1200 E Calfornia Blvd|\nPasadena\, CA 91125\nU
nited States of America)\n\nAbstract: \nCheeger inequalities in spectral g
raph theory help to comment on the approximate connectivity or expansion o
f a graph (a combinatorial property) from the eigenvalues of the adjacency
matrix of the graph (an algebraic property). More specifically\, it says
that the expansion of a graph can be tightly bound by the second largest e
igenvalue of the graph. The Cheeger inequalities were generalized by Lee-G
haran-Trevisan so that the k-way expansion of a graph can be approximated
by the k largest eigenvalues of the adjacency matrix.\n\nIn this talk\, i
will present the higher order cheeger inequality\, which roughly says\, th
at the first k eigenvalues of the laplacian of a graph are close to 0 if a
nd only if we can find k approximately disjoint subsets in the graph. I wi
ll start with the basics and show the inequality.\n\nPaper: https://arxiv.
org/abs/1111.1055\n \n
URL:https://www.tcs.tifr.res.in/web/events/706
DTSTART;TZID=Asia/Kolkata:20160812T160000
DTEND;TZID=Asia/Kolkata:20160812T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR