Sgt/lecture9 - ประวัติรุ่นแก้ไข

Tanee: /* Expander Code */

2015-04-22T10:56:27Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:52:26Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:48:40Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:44:12Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:39:15Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:25:57Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:23:15Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:22:10Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:18:00Z

Expander Code

Tanee: /* Expander Code */

2015-04-22T10:17:37Z

Expander Code

@@ แถว 93: / แถว 93: @@
 จะได้ว่าสำหรับเซต <math>S \subset U</math> และ <math>T \subset V</math> ใดใด
 :<math>\Bigl|\ |E(S,T)| - \frac{d}{n}|S| |T|\Bigr|\ \leq\ \epsilon d\sqrt{|S| |T|}</math>}}
 {{กล่องทฤษฎีบท|ให้ <math>|S| = \sigma n</math> และ <math>|T| = \tau n</math> ดีกรีเฉลี่ยของ <math>G(S \cup T)</math> มีค่าไม่เกิน <math>\frac{2d\sigma\tau}{\sigma + \tau} + \epsilon d</math> }}

@@ แถว 94: / แถว 94: @@
 :<math>\Bigl|\ |E(S,T)| - \frac{d}{n}|S| |T|\Bigr|\ \leq\ \epsilon d\sqrt{|S| |T|}</math>}}
-{{กล่องทฤษฎีบท|สอง}}
+{{กล่องทฤษฎีบท|ให้ <math>|S| = \sigma n</math> และ <math>|T| = \tau n</math> ดีกรีเฉลี่ยของ <math>G(S \cup T)</math> มีค่าไม่เกิน <math>\frac{2d\sigma\tau}{\sigma + \tau} + \epsilon d</math> }}
 {{เริ่มบทพิสูจน์}}
 {{จบบทพิสูจน์}}

@@ แถว 92: / แถว 92: @@
 จะได้ว่าสำหรับเซต <math>S \subset U</math> และ <math>T \subset V</math> ใดใด
-:<math>\abs{\ |E(S,T)| - \frac{d}{n}|S| |T|}\ \leq\ \epsilon d\sqrt{|S| |T|}</math>}}
+:<math>\Bigl|\ |E(S,T)| - \frac{d}{n}|S| |T|\Bigr|\ \leq\ \epsilon d\sqrt{|S| |T|}</math>}}
 {{กล่องทฤษฎีบท|สอง}}
 {{เริ่มบทพิสูจน์}}
 {{จบบทพิสูจน์}}

@@ แถว 89: / แถว 89: @@
 ในสัปดาห์นี้ เราพูดถึงทฤษฎีบทเพิ่มอีกสองทฤษฎีบท
-{{กล่องทฤษฎีบท|ให้ G = <math>(U \cup V,E)</math> เป็น d-regular bipartite graph ที่ approximate <math>\frac{d}{n}K_{n,n}</math>
+{{กล่องทฤษฎีบท|ให้ <math>G = (U \cup V,E)</math> เป็น d-regular bipartite graph ที่ approximate <math>\frac{d}{n}K_{n,n}</math>
 จะได้ว่าสำหรับเซต <math>S \subset U</math> และ <math>T \subset V</math> ใดใด
-<math>|\ |E(S,T)| - \frac{d}{n}|S| |T|\ |\ \leq\ \epsilon d\sqrt{|S| |T|}</math>}}
+:<math>\abs{\ |E(S,T)| - \frac{d}{n}|S| |T|}\ \leq\ \epsilon d\sqrt{|S| |T|}</math>}}
 {{กล่องทฤษฎีบท|สอง}}
 {{เริ่มบทพิสูจน์}}
 {{จบบทพิสูจน์}}

@@ แถว 87: / แถว 87: @@
 Laplacian ของ H จะมี eigenvalue ที่มีค่าเท่ากับ <math>\lambda_i</math> และ <math>|2d - \lambda_i|</math>}}
-ในสัปดาห์นี้ เราพิสูจน์ทฤษฎีบทเพิ่มอีกสองทฤษฎีบท
+ในสัปดาห์นี้ เราพูดถึงทฤษฎีบทเพิ่มอีกสองทฤษฎีบท
-{{กล่องทฤษฎีบท|หนึ่ง}}
+{{กล่องทฤษฎีบท|ให้ G = <math>(U \cup V,E)</math> เป็น d-regular bipartite graph ที่ approximate <math>\frac{d}{n}K_{n,n}</math>
-{{เริ่มบทพิสูจน์}}
+จะได้ว่าสำหรับเซต <math>S \subset U</math> และ <math>T \subset V</math> ใดใด
-{{จบบทพิสูจน์}}
+<math>|\ |E(S,T)| - \frac{d}{n}|S| |T|\ |\ \leq\ \epsilon d\sqrt{|S| |T|}</math>}}
 {{กล่องทฤษฎีบท|สอง}}
 {{เริ่มบทพิสูจน์}}
 {{จบบทพิสูจน์}}

@@ แถว 83: / แถว 83: @@
 กราฟ H จะมีโหนด <math>u_0,u_1</math>
-และสำหรับเส้นเชื่อม <math>(u,v)</math> ใน G จะมีเส้นเชื่อมใน H สองเส้น <math>(u_0,v_1),(u_1,v_0)</math> การบ้านในสัปดาห์นี้คือ การพิสูจน์ข้อความด้านล่าง
+และสำหรับเส้นเชื่อม <math>(u,v)</math> ใน G จะมีเส้นเชื่อมใน H สองเส้น <math>(u_0,v_1),(u_1,v_0)</math> และการบ้านในสัปดาห์นี้คือ การพิสูจน์ข้อความด้านล่าง
 {{กล่องทฤษฎีบท|ให้ H เป็น double-cover ของ G จะได้ว่าสำหรับทุก eigenvalue <math>\lambda_i</math> ของ Laplacian ของ G จะได้ว่า
 Laplacian ของ H จะมี eigenvalue ที่มีค่าเท่ากับ <math>\lambda_i</math> และ <math>|2d - \lambda_i|</math>}}

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:22, 22 เมษายน 2558
แถว 84:		แถว 84:

	และสำหรับเส้นเชื่อม <math>(u,v)</math> ใน G จะมีเส้นเชื่อมใน H สองเส้น <math>(u_0,v_1),(u_1,v_0)</math>		และสำหรับเส้นเชื่อม <math>(u,v)</math> ใน G จะมีเส้นเชื่อมใน H สองเส้น <math>(u_0,v_1),(u_1,v_0)</math>
		+
		+	{{กล่องทฤษฎีบท\|ให้ H เป็น double-cover ของ G จะได้ว่าสำหรับทุก eigenvalue <math>\lambda_i</math> ของ Laplacian ของ G จะได้ว่า
		+	Laplacian ของ H จะมี eigenvalue ที่มีค่าเท่ากับ <math>\lambda_i</math> และ <math>\|2d - \lambda_i\|</math>}}

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:18, 22 เมษายน 2558
แถว 83:		แถว 83:
	กราฟ H จะมีโหนด <math>u_0,u_1</math>		กราฟ H จะมีโหนด <math>u_0,u_1</math>

−	และสำหรับเส้นเชื่อม <math>(u,v)</math> ใน G ~~จะมีเส้นเชื่อมสองเส้นใน~~ H <math>(u_0,v_1),(u_1,v_0)</math>	+	และสำหรับเส้นเชื่อม <math>(u,v)</math> ใน G จะมีเส้นเชื่อมใน H สองเส้น <math>(u_0,v_1),(u_1,v_0)</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:17, 22 เมษายน 2558
แถว 77:		แถว 77:
	นั่นคือ eigenvalue <math>\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_{2n}</math> ของ Laplacian ของกราฟ G มีคุณสมบัติดังนี้		นั่นคือ eigenvalue <math>\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_{2n}</math> ของ Laplacian ของกราฟ G มีคุณสมบัติดังนี้
	<math>\lambda_1 = 0\ ,\ \lambda_{2n} = 2d\ ,\ \|\lambda_i-d\|\leq \epsilon d\ ;\ 1 < i < 2n</math>		<math>\lambda_1 = 0\ ,\ \lambda_{2n} = 2d\ ,\ \|\lambda_i-d\|\leq \epsilon d\ ;\ 1 < i < 2n</math>
		+
		+	เราสามารถสร้างกราฟที่มีคุณสมบัติตามต้องการได้โดยการสร้าง double-cover ของ expander graph โดยนิยามดังนี้
		+
		+	กราฟ H เป็น double-cover ของกราฟ G เมื่อ H เป็นกราฟที่มีจำนวนโหนดและเส้นเชื่อมเป็นสองเท่าของ G โดยสำหรับทุกโหนด u ของ G
		+	กราฟ H จะมีโหนด <math>u_0,u_1</math>
		+
		+	และสำหรับเส้นเชื่อม <math>(u,v)</math> ใน G จะมีเส้นเชื่อมสองเส้นใน H <math>(u_0,v_1),(u_1,v_0)</math>