BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20221110T120000Z
UID:967f3509d52d205f0c55ddb434248821-354
DTSTAMP:19700101T120021Z
DESCRIPTION:Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/354/cheeger-inequalities-for-vertex-expansion-and-reweighted-eigenvalues/
SUMMARY:The classical Cheegers inequality relates the edge conductance ψ of a graph and the second smallest eigenvalue λ2 of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality ψ2 / log |V| ≲ λ2* ≲ ψ connecting the vertex expansion ψ of a graph G=(V,E) and the maximum reweighted second smallest eigenvalue λ2* of the Laplacian matrix.

In this work, we first improve their result to  ψ2 / log d ≲ λ2* ≲ ψ where d is the maximum degree in G, which is optimal up to a constant factor. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. Building on this connection, we then develop a new spectral theory for vertex expansion. We discover that several interesting generalizations of Cheeger inequalities relating edge conductances and eigenvalues have a close analog in relating vertex expansions and reweighted eigenvalues. These include an analog of Trevisans result on bipartiteness, an analog of higher order Cheegers inequality, and an analog of improved Cheegers inequality.

Finally, inspired by this connection, we present negative evidence to the 0/1-polytope edge expansion conjecture by Mihail and Vazirani. We construct 0/1-polytopes whose graphs have very poor vertex expansion. This implies that the fastest mixing time to the uniform distribution on the vertices of these 0/1-polytopes is almost linear in the graph size. This does not provide a counterexample to the conjecture, but this is in contrast with known positive results which proved poly-logarithmic mixing time to the uniform distribution on the vertices of subclasses of 0/1-polytopes.

Speaker website: https://cs.uwaterloo.ca/~lapchi/

For more details please visit: https://www.csa.iisc.ac.in/iisc-msr-seminar/

Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d


Hosts: Rahul Madhavan and Rameesh Paul
DTSTART:20221110T120000Z
END:VEVENT
END:VCALENDAR