Sgt/lecture5

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

(not yet finished)

สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ในหา upper bound ของ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 ($\gamma _{2}$) ของ normalized laplacian matrix ของ graph

Conductance

จาก lecture 3 ได้กล่าวถึง isoperimetric inequality ว่าด้วย lower bound ของ cut ไปแล้ว [1] นั้น สำหรับ unweighted undirected graph $G=(V,E)$ และ $S\subset V$ และ cut $\partial (S)=\{(u,v)\in E,u\in S,v\notin S\}$

นิยาม "conductance ของ subgraph" ($\phi (S)$) และ "conductance ของ graph" ($\phi (G)$) ดังต่อไปนี้

${\begin{aligned}\phi (S)&={\frac {|\partial (S)|}{min(d(S),d(V-S))}}\\\phi (G)&=\min _{S\subset V}\phi (S)\end{aligned}}$

$\phi (G)\leq {\sqrt {2\gamma _{2}}}$

$\gamma _{2}$ หมายถึง eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (จะอธิบายในส่วนถัดไป)