Sgt/lecture4

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

ในสัปดาห์นี้ เราได้พูดถึง Courant–Fischer Theorem

Courant–Fischer Theorem

ให้ A เป็น symmetric matrix ขนาด n ที่มี eigen value $\mu _{1}\geq \mu _{2}\geq \ldots \geq \mu _{n}$ (สังเกตว่าเรียงสลับด้านกับ $\lambda$ ในเลคเชอร์อื่นๆ)

เราจะได้ว่า

${\begin{aligned}\mu _{k}&=\max \limits _{S\subseteq \mathbb {R} ^{n}\ ;\ dim(S)=k}&&\min _{x\in S\ ;\ x\neq {\bar {0}}}{\frac {x^{T}Ax}{x^{T}x}}\\&=\min \limits _{T\subseteq \mathbb {R} ^{n}\ ;\ dim(T)=n-k+1}&&\max _{x\in S\ ;\ x\neq {\bar {0}}}{\frac {x^{T}Ax}{x^{T}x}}\end{aligned}}$

---

To be proved...

---

Graphic Inequality

เป็นการเปรียบเทียบกราฟโดยให้ sense ของการ "มากกว่า" "น้อยกว่า" เหมือนการเปรียบเทียบจำนวนจริง
ให้ A เป็น matrix ใดๆ เราเขียนแทนว่า A เป็น positive semi-definite ด้วย $A\succeq 0$ โดยนิยามดังนี้

$A\succeq 0$ เมื่อและต่อเมื่อ $\forall \psi \in \mathbb {R} ^{n}\ ;\ \psi ^{T}A\psi \geq 0$

และสำหรับ matrix A,B ใดๆ เราเขียนแทนว่า $A\succeq B$ เมื่อและต่อเมื่อ $A-B\succeq 0$ ความสัมพันธ์นี้มีคุณสมบัติถ่ายทอด คือถ้า $A\succeq B;B\succeq C$ จะได้ว่า $A\succeq C$

ทำนองเดียวกัน สำหรับกราฟ G,H ใดๆ เราแทนว่า $G\succeq H$ เมื่อและต่อเมื่อ $L_{G}\succeq L_{H}$ และสังเกตว่า ถ้า H เป็น subgraph ของ G จะได้ว่า $G\succeq H$

และสำหรับจำนวนจริง c ใดๆเราเขียนแทน $G\succeq c\cdot H$ หมายถึง $L_{G}\succeq c\cdot L_{H}$

จากนิยามข้างต้น เราจะได้คุณสมบัติว่า (ในเนื้อหาครั้งนี้ไม่มีการพิสูจน์ทฤษฎีบทนี้)

ถ้า G,H เป็นกราฟที่มีคุณสมบัติว่า

Path Inequality

ให้กราฟขนาด n โหนด $G_{1,n}\ ,P_{n}$ แทนกราฟที่มีเส้นเชื่อมเดียว (1,n) และกราฟที่มีเส้นเชื่อม n-1 เส้น $(1,2),(2,3),\ldots ,(n-1,n)$ ตามลำดับ

$(n-1)P_{n}\succeq G_{n}$

TO BE CONTINUED