ในทฤษฎีกราฟกราฟขยายเป็นกราฟเบาบางที่มีคุณสมบัติการเชื่อมต่อ ที่แข็งแกร่ง ซึ่งวัดปริมาณโดยใช้การขยาย จุดยอดขอบหรือสเปกตรัมการสร้างกราฟขยายได้ก่อให้เกิดการวิจัยในคณิตศาสตร์บริสุทธิ์และคณิตศาสตร์ประยุกต์ โดยมีการประยุกต์ใช้หลายอย่างในทฤษฎีความซับซ้อนการออกแบบเครือข่ายคอมพิวเตอร์ ที่แข็งแกร่ง และทฤษฎีรหัสแก้ไขข้อผิดพลาด^{[ 1 ]}

โดยสัญชาตญาณแล้ว กราฟขยาย (expander graph) คือมัลติกราฟ แบบไม่มีทิศทางที่มีจำนวนจำกัด ซึ่งเซตย่อยของจุดยอดทุกเซตที่ไม่ "ใหญ่เกินไป" จะมีขอบเขตที่ "ใหญ่" การกำหนดรูปแบบที่เป็นทางการที่แตกต่างกันของแนวคิดเหล่านี้ทำให้เกิดแนวคิดของตัวขยายที่แตกต่างกัน ได้แก่ตัวขยายขอบ ( edge ​​expanders) ตัวขยายจุดยอด (vertex expanders ) และตัวขยายสเปกตรัม (spectral expanders ) ดังที่ได้นิยามไว้ด้านล่าง

กราฟที่ไม่เชื่อมต่อกันไม่ใช่กราฟขยาย เนื่องจากขอบเขตของส่วนประกอบที่เชื่อมต่อกันนั้นว่างเปล่า กราฟจำกัดที่เชื่อมต่อกันทุกกราฟเป็นกราฟขยายได้ อย่างไรก็ตาม กราฟที่เชื่อมต่อกันต่างกันจะมีพารามิเตอร์การขยายที่แตกต่างกันกราฟสมบูรณ์มีคุณสมบัติการขยายที่ดีที่สุด แต่ก็มีดีกรี สูงสุดที่เป็นไป ได้ โดยทั่วไปแล้ว กราฟจะเป็นกราฟขยายที่ดีหากมีดีกรีต่ำและพารามิเตอร์การขยายสูง

การขยายขอบ (หรือเรียกอีกอย่างว่าจำนวนไอโซเพอริเมตริกหรือค่าคงที่ชีเกอร์ ) h ( G )ของกราฟGบน จุดยอด nจุด ถูกกำหนดดังนี้

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}$

ที่ไหน${\displaystyle \partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\notin S\},}$

ซึ่งสามารถเขียนได้อีกแบบว่า∂ S = E ( S , S ) โดยที่S  := V ( G ) \ Sเป็นส่วนเติมเต็มของSและ

${\displaystyle E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}}$

ขอบระหว่างเซตย่อยของจุดยอด A , B ⊆ V ( G )

ในสมการ ค่าต่ำสุดจะอยู่เหนือเซตS ที่ไม่ว่างทั้งหมดซึ่ง ^มี จุดยอด ไม่เกินn ⁄ 2จุด และ∂ SคือขอบเขตขอบของSกล่าวคือ เซตของขอบที่มีจุดปลายเพียงจุดเดียวในS [ ^{2 ]}

โดยสัญชาตญาณ

${\displaystyle \min {|\partial S|}=\min |E({S},{\overline {S}})|}$

จำนวนขอบขั้นต่ำที่ต้องตัดเพื่อแบ่งกราฟออกเป็นสองส่วน การขยายขอบเป็นการปรับแนวคิดนี้ให้เป็นมาตรฐานโดยการแบ่งด้วยจำนวนจุดยอดที่น้อยที่สุดในสองส่วนนั้น เพื่อดูว่าการปรับให้เป็นมาตรฐานสามารถเปลี่ยนแปลงค่าได้อย่างมากเพียงใด ลองพิจารณาตัวอย่างต่อไปนี้ สมมติว่ามีกราฟสมบูรณ์สองกราฟที่มีจำนวนจุดยอดเท่ากันคือnและเพิ่ม ขอบ nเส้นระหว่างสองกราฟโดยเชื่อมต่อจุดยอดแบบหนึ่งต่อหนึ่ง จำนวนขอบขั้นต่ำที่ต้องตัดจะเป็นnแต่การขยายขอบจะเป็น 1

โปรดสังเกตว่าในmin | ∂ S |การหาค่าเหมาะสมที่สุดสามารถทำได้อย่างเทียบเท่ากันทั้งบน0 ≤ | S | ≤ n ⁄ 2หรือบนเซตย่อยที่ไม่ว่างเปล่าใดๆ เนื่องจาก . แต่สิ่งเดียวกันนี้ไม่เป็นจริงสำหรับh ( G )เนื่องจากการปรับขนาดโดย| S |หากเราต้องการเขียนh ( G )ด้วยการหาค่าเหมาะสมที่สุดบนเซตย่อยที่ไม่ว่างเปล่าทั้งหมด เราสามารถเขียนใหม่ได้เป็น ${\displaystyle E(S,{\overline {S}})=E({\overline {S}},S)}$

${\displaystyle h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {|E({S},{\overline {S}})|}{\min\{|S|,|{\overline {S}}|\}}}.}$

จำนวนไอโซเพอริเมตริกของจุดยอดh _out ( G ) (หรือการขยายหรือการเพิ่มขนาดของ จุดยอด ) ของกราฟGถูกกำหนดดังนี้

${\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}$

โดยที่∂ _out ( S )คือขอบเขตภายนอกของSกล่าวคือ เซตของจุดยอดในV ( G ) \ Sที่มีเพื่อนบ้านอย่างน้อยหนึ่งจุดในS ^{[ 3 ]}ในรูปแบบอื่นของคำจำกัดความนี้ (เรียกว่าการขยายเพื่อนบ้านที่ไม่ซ้ำกัน ) ∂ _out ( S )จะถูกแทนที่ด้วยเซตของจุดยอดในVที่มี เพื่อนบ้าน เพียงหนึ่งจุดในS ^{[ 4 ]}

จำนวนไอโซเพอริเมตริกจุดยอดh _ใน ( G )ของกราฟGถูกกำหนดดังนี้

${\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}$

โดยที่ขอบเขตภายในของSคือเซตของจุดยอดในSที่มีเพื่อนบ้านอย่างน้อยหนึ่งจุดในV ( G ) ^\ S [ ^{3 ]}${\displaystyle \partial _{\text{in}}(S)}$

เมื่อGเป็นd -regularนิยาม การขยายเชิง พีชคณิตเชิงเส้นสามารถทำได้โดยอาศัยค่าลักษณะเฉพาะของเมทริกซ์ประชิดA = A ( G )ของGโดยที่Aijคือจำนวนขอบระหว่างจุดยอดiและj ^{[ 5} ] เนื่องจากAเป็นเมทริกซ์สมมาตร^{ทฤษฎีบท}_{สเปกตรัม}บ่งชี้ว่าAมีค่าลักษณะเฉพาะที่เป็นจำนวนจริงn ค่า λ1 ≥ λ2 _≥ … ≥ λnเป็นที่ทราบกันว่าค่าลักษณะเฉพาะเหล่านี้ทั้งหมดอยู่ในช่วง_[ −d , d ]และโดยเฉพาะอย่างยิ่งเป็นที่ทราบกันว่าλn = −dก็ต่อเมื่อGเป็นเมทริกซ์ _{สองส่วน}

กล่าวอย่างเป็นทางการมากขึ้น เราจะเรียก กราฟที่มี nจุดยอดและdมิติแบบปกติว่า...

${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$

ในฐานะกราฟ ( n , d , λ )ขอบเขตที่กำหนดโดย_กราฟ ( n , d , λ )บนλiสำหรับi ≠ 1มีประโยชน์ในหลายบริบท รวมถึงทฤษฎีบท การผสมตัวขยาย

การขยายสเปกตรัมสามารถเป็นแบบสองด้านได้ดังที่กล่าวมาข้างต้น โดยที่หรืออาจเป็นแบบด้านเดียวได้ โดยที่แนวคิดหลังนี้เป็นแนวคิดที่อ่อนกว่าซึ่งใช้ได้กับกราฟสองส่วนและยังคงมีประโยชน์สำหรับการใช้งานหลายอย่าง เช่น บทพิสูจน์ของ Alon–Chung ^{[ 6 ]}${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$${\displaystyle \max _{i\neq 1}\lambda _{i}\leq \lambda }$

เนื่องจากGเป็นกราฟปกติ การกระจายแบบเอกรูปที่มีu _i = 1 ⁄ nสำหรับทุกi = 1, …, nจึงเป็นการกระจายแบบคงที่ของGนั่นคือ เรามีAu = duและuเป็นเวกเตอร์ ลักษณะเฉพาะ ของAที่มีค่าลักษณะเฉพาะλ ₁ = dโดยที่dคือดีกรีของจุดยอดของGช่องว่างสเปกตรัมของGถูกกำหนดให้เป็น^d − λ 2 _และมันวัดการขยายสเปกตรัมของกราฟG [ ^{7 ]}${\displaystyle u\in \mathbb {R} ^{n}}$

ถ้าเราตั้ง

${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$

เนื่องจากค่านี้เป็นค่าไอเกนที่ใหญ่ที่สุดที่สอดคล้องกับเวกเตอร์ไอเกนที่ตั้งฉากกับuจึงสามารถนิยามได้อย่างเทียบเท่าโดยใช้ค่าสัมประสิทธิ์เรย์ลี :

${\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}$

ที่ไหน

${\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}$

คือค่านอร์ม 2ของเวกเตอร์ ${\displaystyle v\in \mathbb {R} ^{n}}$

นิยามในรูปแบบมาตรฐานเหล่านี้ก็มีการใช้งานอย่างแพร่หลายและสะดวกกว่าในการระบุผลลัพธ์บางอย่าง ในที่นี้จะพิจารณาเมทริกซ์⁠1/งAคือเมทริกซ์การเปลี่ยนสถานะแบบมาร์คอฟของกราฟ Gค่าลักษณะเฉพาะของเมทริกซ์นี้อยู่ระหว่าง -1 และ 1 สำหรับกราฟที่ไม่จำเป็นต้องเป็นกราฟปกติ สเปกตรัมของกราฟสามารถกำหนดได้ในทำนองเดียวกันโดยใช้ค่าลักษณะเฉพาะของเมทริกซ์ลาปลาเซียนสำหรับกราฟ แบบมีทิศทางเราจะพิจารณาค่าเอกฐานของเมทริกซ์ประชิด Aซึ่งเท่ากับรากของค่าลักษณะเฉพาะของเมทริกซ์สมมาตร A ^T A

กลุ่มกราฟปกติที่มีขนาดเพิ่มขึ้นเรื่อยๆ เรียกว่ากลุ่มขยายถ้ามีค่าห่างจากศูนย์^{[ 8 ]}${\displaystyle (G_{i})_{i\in \mathbb {N} }}$${\displaystyle d}$${\displaystyle h(G_{i})}$

พารามิเตอร์การขยายที่ กำหนด ไว้ข้างต้นมีความสัมพันธ์กัน โดยเฉพาะอย่างยิ่ง สำหรับกราฟd- ปกติใดๆ G

${\displaystyle h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).}$

ดังนั้น สำหรับกราฟที่มีดีกรีคงที่ การขยายจุดยอดและการขยายขอบจึงมีลักษณะเหมือนกันในเชิงคุณภาพ

เมื่อGเป็น กราฟ d-ปกติ หมายความว่าแต่ละจุดยอดมีดีกรีdจะมีความสัมพันธ์ระหว่างค่าคงที่ไอโซเพอริเมตริก_h ( G )และช่องว่างd − λ2ในสเปกตรัมของตัวดำเนินการประชิดของGตามทฤษฎีกราฟสเปกตรัมมาตรฐาน ค่าไอเกนที่ไม่สำคัญของตัวดำเนินการประชิดของ^กราฟ d-ปกติคือ λ1 = dและค่า_ไอเกนที่ไม่สำคัญตัวแรกคือ_λ2 ถ้า G เชื่อมต่อกันแล้วλ2 < dอสมการเนื่องจาก Dodziuk ^[ ₉ ^]และAlonและMilman ^{[ 10 ]}ระบุว่า^{[ 11 ]}

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

ในความเป็นจริง ขอบล่างนั้นแน่น ขอบล่างบรรลุได้ในขีดจำกัดสำหรับไฮเปอร์คิวบ์Q _nโดยที่h ( G ) = 1และd – λ ₂ = 2ขอบบนบรรลุได้ (ในเชิงอะซิมโทติก) สำหรับวัฏจักร โดยที่h ( C _n ) = 4/ n = Θ(1/ n )และd – λ ₂ = 2 – 2cos(2 / n ) ≈ (2 / n ) ² = Θ(1/ n ² )${\displaystyle \pi }$${\displaystyle \pi }$ [ ^{1 ]}ขอบเขตที่ดีกว่านี้กำหนดไว้^{ใน[ 12 ]}ดังนี้

${\displaystyle h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.}$

ความไม่เท่าเทียมกันเหล่านี้มีความเกี่ยวข้องอย่างใกล้ชิดกับขอบเขตของ Cheegerสำหรับลูกโซ่ Markovและสามารถมองได้ว่าเป็นเวอร์ชันแบบไม่ต่อเนื่องของความไม่เท่าเทียมกันของ Cheegerในเรขาคณิตแบบ Riemannian

การเชื่อมโยงที่คล้ายกันระหว่างตัวเลขไอโซเพอริเมตริกจุดยอดและช่องว่างสเปกตรัมได้รับการศึกษาแล้วเช่นกัน: ^{[ 13 ]}

${\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}$

${\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}$

กล่าวโดยนัยเชิงอะซิ ม โทติก ปริมาณh ² ⁄ d , h _outและh _in ²ล้วนมีขอบเขตบนโดยช่องว่างสเปกตรัมO ( d – λ ₂ )

มีกลยุทธ์ทั่วไปสี่ประการสำหรับการสร้างตระกูลกราฟขยายอย่างชัดเจน^{[ 14 ]}กลยุทธ์แรกเป็นแบบพีชคณิตและทฤษฎีกลุ่ม กลยุทธ์ที่สองเป็นแบบวิเคราะห์และใช้การจัดเรียงแบบบวกกลยุทธ์ที่สามเป็นแบบเชิงการจัดเรียงและใช้ ผลคูณกราฟ แบบซิกแซกและที่เกี่ยวข้อง และกลยุทธ์ที่สี่ขึ้นอยู่กับการยกNoga Alonแสดงให้เห็นว่ากราฟบางกราฟที่สร้างจากเรขาคณิตจำกัดเป็นตัวอย่างที่เบาบางที่สุดของกราฟขยายสูง^{[ 15 ]}

การสร้าง เชิงพีชคณิตโดยใช้กราฟ Cayleyเป็นที่รู้จักสำหรับกราฟขยายรูปแบบต่างๆ การสร้างต่อไปนี้เป็นผลงานของ Margulis และได้รับการวิเคราะห์โดย Gabber และ Galil ^{[ 16 ]}สำหรับจำนวนธรรมชาติn ทุกจำนวน เราพิจารณากราฟG _nที่มีเซตจุดยอดโดยที่: สำหรับจุดยอดทุกจุดจุดยอดที่อยู่ติดกันแปดจุดของจุดยอดนั้นคือ ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$

${\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}$

ดังนั้นจึงเป็นดังต่อไปนี้:

ทฤษฎีบทสำหรับทุกค่าnกราฟG _nมีค่าไอเกนที่ใหญ่เป็นอันดับสอง${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$

ตามทฤษฎีบทของ Alon และ Boppanaกราฟd -regular ขนาดใหญ่เพียงพอทั้งหมด จะสอดคล้องกับ โดยที่λ ₂คือค่าลักษณะเฉพาะที่ใหญ่เป็นอันดับสองในค่าสัมบูรณ์^{[ 17 ]}ผลที่ตามมาโดยตรงคือเรารู้ว่าสำหรับdและ ที่กำหนดไว้ทุกค่า จะมีกราฟ( n , d , λ ) เพียงจำนวนจำกัดเท่านั้น กราฟ Ramanujanเป็น กราฟ d -regular ที่ขอบเขตนี้แน่น ซึ่งสอดคล้องกับ^{[ 18 ]}${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$${\displaystyle \lambda <2{\sqrt {d-1}}}$

${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.}$

_{ดังนั้นกราฟ Ramanujan จึง}มีค่าλ² ที่เล็กที่สุดในเชิงอะซิมโทติก ทำให้กราฟเหล่านี้เป็นเครื่องมือขยายสเปกตรัมที่ยอดเยี่ยม

Lubotzky , Phillips และSarnak (1988), Margulis (1988) และ Morgenstern (1994) แสดงให้เห็นว่าสามารถสร้างกราฟ Ramanujan ได้อย่างชัดเจน^{[ 19 ]}

ในปี พ.ศ. 2528 Alon ตั้งข้อสันนิษฐานว่ากราฟd- ปกติส่วนใหญ่บนจุดยอด nจุด สำหรับn ที่มีขนาดใหญ่พอสมควร เกือบจะเป็นกราฟ Ramanujan ^{[ 20 ]}นั่นคือ สำหรับε > 0กราฟเหล่านั้นจะสอดคล้องกับ

${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$.

ในปี พ.ศ. 2546 โจเอล ฟรีดแมนได้พิสูจน์สมมติฐานและระบุความหมายของ " กราฟ d-ปกติส่วนใหญ่" โดยแสดงให้เห็นว่ากราฟd- ปกติ แบบสุ่มมีสำหรับทุกε > 0ด้วยความน่าจะเป็น1 – O ( n ^-τ )โดยที่^{[ 21 ] [ 22 ]}${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$

${\displaystyle \tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .}$

Puder ได้ให้การพิสูจน์ที่ง่ายกว่าสำหรับผลลัพธ์ที่อ่อนกว่าเล็กน้อย^{[ 23 ] [ 24 ] [ 25 ]}

Marcus , SpielmanและSrivastava [ ^{26 ] [ 27 ]}ได้สร้าง กราฟ Ramanujan แบบสองส่วน^โดยอาศัยลิฟต์

ในปี 2024 บทความฉบับร่างโดย Jiaoyang Huang, Theo McKenzie และHorng-Tzer Yauได้พิสูจน์ว่า

${\displaystyle \lambda \leq 2{\sqrt {d-1}}}$.

โดยมีสัดส่วนของค่าลักษณะเฉพาะที่กระทบขอบเขต Alon-Boppana ประมาณ 69% จากการพิสูจน์ว่าความเป็นสากลของขอบเป็นจริง นั่นคือ พวกมันเป็นไปตามการกระจาย Tracy-Widomที่เกี่ยวข้องกับGaussian Orthogonal Ensemble ^{[ 28 ] [ 29 ]}

Reingold , VadhanและWigdersonได้นำเสนอผลคูณแบบซิกแซกในปี 2000 ^{[ 30 ]} โดยคร่าวๆ แล้ว ผลคูณแบบซิกแซกของกราฟขยายสองกราฟจะสร้างกราฟที่มีการขยายที่แย่ลงเพียงเล็กน้อย ดังนั้น ผลคูณแบบซิกแซกจึงสามารถใช้สร้างตระกูลของกราฟขยายได้เช่นกัน ถ้าGเป็น กราฟ ( n , d , λ ₁ )และHเป็น กราฟ ( m , d , λ ₂ )แล้ว ผลคูณแบบซิกแซกG ◦ Hจะเป็น กราฟ ( nm , d ² , φ ( λ ₁ , λ ₂ ))โดยที่φมีคุณสมบัติดังต่อไปนี้

1. ถ้าแล₁ < 1และแล₂ < 1แล้วφ ( แล₁ , แล₂ ) < 1 ;
2. φ ( แลมบ์ดา₁ , แลมบ์ดา₂ ) ≤ เลม₁ + แลมบ์₂ .

โดยเฉพาะ^{[ 30 ]}

${\displaystyle \phi (\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}.}$

โปรดทราบว่าคุณสมบัติ (1) บ่งชี้ว่าผลคูณซิกแซกของกราฟขยายสองกราฟก็เป็นกราฟขยายเช่นกัน ดังนั้นผลคูณซิกแซกจึงสามารถใช้แบบอุปนัยเพื่อสร้างตระกูลของกราฟขยายได้

โดยสัญชาตญาณแล้ว การสร้างผลคูณแบบซิกแซกสามารถคิดได้ในลักษณะต่อไปนี้ แต่ละจุดยอดของGจะถูกขยายออกเป็น "กลุ่ม" ของ จุดยอด mจุด โดยแต่ละจุดยอดจะเชื่อมโยงกับขอบที่แตกต่างกันซึ่งเชื่อมต่อกับจุดยอดนั้น แต่ละจุดยอดจะถูกกำหนดป้ายกำกับเป็น( v , k )โดยที่vหมายถึงจุดยอดดั้งเดิมของGและkหมายถึง ขอบที่ kของvจุดยอดสองจุด( v , k )และ( w , ℓ )จะเชื่อมต่อกันหากสามารถเคลื่อนที่จาก( v , k )ไปยัง( w , ℓ )ได้ตามลำดับการเคลื่อนที่ต่อไปนี้

1. ซิก – เคลื่อนที่จาก( v , k )ไปยัง( v , k' )โดยใช้ขอบของH
2. กระโดดข้ามก้อนเมฆโดยใช้ขอบk'ในGเพื่อไปยัง( w , ℓ′ )
3. Zag – ย้ายจาก( w , ℓ′ )ไปยัง⁽ w , ℓ )โดยใช้ขอบของH ^{[ 30} ]

r -liftของกราฟถูกสร้างขึ้นโดยการแทนที่จุดยอดแต่ละจุดด้วยจุด ยอด rจุด และขอบแต่ละขอบด้วยการจับคู่ระหว่างเซตของจุดยอดที่สอดคล้องกัน กราฟที่ยกขึ้นจะสืบทอดค่าลักษณะเฉพาะของกราฟเดิม และมีค่าลักษณะเฉพาะเพิ่มเติมบางส่วน Bilu และLinial ^{[ 31 ] [ 32 ]} แสดงให้เห็นว่ากราฟ d -regular ทุกกราฟมี 2-lift ซึ่งค่าลักษณะเฉพาะเพิ่มเติมมีขนาดไม่เกิน พวกเขายังแสดงให้เห็นว่าหากกราฟเริ่มต้นเป็นตัวขยายที่ดีพอ ก็สามารถหา 2-lift ที่ดีได้ในเวลาพหุนามดังนั้นจึงสร้าง ตัวขยาย d -regular ที่มีประสิทธิภาพสำหรับทุก d${\displaystyle r}$${\displaystyle O({\sqrt {d\log ^{3}d}})}$

Bilu และ Linial ตั้งข้อสันนิษฐานว่าขอบเขตสามารถปรับปรุงได้เป็นซึ่งจะเป็นค่าที่เหมาะสมที่สุดเนื่องจากขอบเขต Alon–Boppanaข้อสันนิษฐานนี้ได้รับการพิสูจน์แล้วในการตั้งค่าแบบสองส่วนโดยMarcus , SpielmanและSrivastava ^{[ 26 ] [ 27 ]}ซึ่งใช้วิธีของพหุนามที่สลับกัน ส่งผลให้พวกเขาสร้างกราฟ Ramanujan แบบสองส่วน ขึ้นมาใหม่ การพิสูจน์แบบไม่สร้างดั้งเดิมถูกเปลี่ยนเป็นอัลกอริทึมโดย Michael B. Cohen ^{[ 33 ]}ต่อมาวิธีการนี้ได้รับการขยายไปสู่​​r -lifts โดย Hall, Puder และ Sawin ^{[ 34 ]}${\displaystyle O({\sqrt {d\log ^{3}d}})}$${\displaystyle 2{\sqrt {d-1}}}$

มีผลลัพธ์มากมายที่แสดงให้เห็นถึงการมีอยู่ของกราฟที่มีคุณสมบัติการขยายที่ดีผ่านการโต้แย้งเชิงความน่าจะเป็น อันที่จริง การมีอยู่ของตัวขยายได้รับการพิสูจน์ครั้งแรกโดย Pinsker [ 35 ] ซึ่งแสดงให้เห็นว่าสำหรับกราฟสองส่วนปกติ d ด้านซ้ายที่มีจุดยอด n จุดที่เลือกแบบสุ่ม | N ^{( S )} | ≥ ( d – 2 ) | S |สำหรับเซตย่อยทั้งหมดของจุดยอด| S | ≤ c _d nด้วยความน่าจะเป็นสูงโดยที่c _dเป็นค่าคงที่ที่ขึ้นอยู่กับdซึ่งคือO ( d ^-4 ) Alon และ Roichman ^{[ 36 ]}แสดงให้เห็นว่าสำหรับทุก1 > ε > 0จะมีc ( ε ) > 0 บาง ค่าที่ทำให้สิ่งต่อไปนี้เป็นจริง: สำหรับกลุ่มGที่มีอันดับnให้พิจารณากราฟ Cayley บนGที่มี องค์ประกอบ c ( ε ) log ₂ nที่เลือกแบบสุ่มจากGจากนั้น ในกรณีที่nเข้าใกล้ค่าอนันต์ กราฟที่ได้จะเป็นกราฟขยาย ε อย่างแน่นอน

ในปี 2021 อเล็กซานเดอร์ได้ปรับเปลี่ยนอัลกอริธึม MCMC เพื่อค้นหาโครงสร้างแบบสุ่มเพื่อสร้างกราฟ Ramanujan ที่มีขนาดจุดยอดคงที่และระดับความสม่ำเสมอ^{[ 37 ]}ผลลัพธ์แสดงให้เห็นว่ากราฟ Ramanujan มีอยู่สำหรับทุกคู่ขนาดจุดยอดและระดับจนถึง 2000 จุดยอด

ในปี 2024 Alon ได้สร้างวิธีการสร้างกราฟใกล้เคียง Ramanujan ที่ชัดเจนสำหรับทุกคู่ขนาดจุดยอดและดีกรี

แรงจูงใจดั้งเดิมสำหรับการสร้างเอ็กซ์แพนเดอร์คือการสร้างเครือข่ายที่แข็งแกร่งและประหยัด (เช่น เครือข่ายโทรศัพท์หรือคอมพิวเตอร์): เอ็กซ์แพนเดอร์ที่มีดีกรีจำกัดคือ กราฟที่แข็งแกร่งในเชิงอะซิมโทติก โดยจำนวนขอบจะเพิ่มขึ้นเป็นเส้นตรงตามขนาด (จำนวนจุดยอด) สำหรับทุกเซตย่อย

กราฟขยาย (Expander graphs) มีการประยุกต์ใช้อย่างกว้างขวางในวิทยาศาสตร์คอมพิวเตอร์ในการออกแบบอัลกอริธึมรหัสแก้ไขข้อผิดพลาดตัวแยกข้อมูลตัวสร้างเลขสุ่มเทียมเครือข่ายเรียง ลำดับ ( Ajtai, Komlós & Szemerédi (1983) ) และ เครือข่าย คอมพิวเตอร์ ที่ทนทาน นอกจากนี้ยังถูกใช้ในการพิสูจน์ผลลัพธ์ที่สำคัญหลายอย่างในทฤษฎีความซับซ้อนของการคำนวณเช่นSL  =  L ( Reingold (2008) ) และทฤษฎีบท PCP ( Dinur (2007) ) ในด้านการเข้ารหัสกราฟขยายถูกใช้เพื่อสร้างฟังก์ชันแฮช

ในการสำรวจกราฟขยายในปี 2006 Hoory, Linial และ Wigderson ได้แบ่งการศึกษาเกี่ยวกับกราฟขยายออกเป็นสี่ประเภท ได้แก่ปัญหาเชิงสุดขั้วพฤติกรรมทั่วไป การสร้างแบบชัดเจน และอัลกอริทึม ปัญหาเชิงสุดขั้วมุ่งเน้นไปที่การกำหนดขอบเขตของพารามิเตอร์การขยาย ในขณะที่ปัญหาพฤติกรรมทั่วไปจะอธิบายลักษณะการกระจายตัวของพารามิเตอร์การขยายบนกราฟสุ่มการสร้างแบบชัดเจนมุ่งเน้นไปที่การสร้างกราฟที่ปรับพารามิเตอร์บางอย่างให้เหมาะสมที่สุด และคำถามเกี่ยวกับอัลกอริทึมศึกษาการประเมินและการประมาณค่าพารามิเตอร์

ทฤษฎีบทการผสมแบบขยายระบุว่า สำหรับ กราฟ ( n , d , λ )สำหรับเซตย่อยสองเซตใดๆ ของจุดยอดS , T ⊆ Vจำนวนขอบระหว่างSและTจะมีค่าประมาณเท่ากับที่คุณคาดหวังใน กราฟ d- ปกติแบบสุ่ม การประมาณค่าจะดีขึ้นเมื่อλ มีค่าน้อยลง ในกราฟ d- ปกติ แบบสุ่มเช่นเดียวกับในกราฟสุ่ม Erdős–Rényiที่มีความน่าจะเป็นของขอบd / nเราคาดหวังว่าจะมี ขอบ d / n • | S | • | T |ระหว่างSและT

กล่าวอย่างเป็นทางการมากขึ้น ให้E ( S , T )แทนจำนวนขอบระหว่างSและTถ้าเซตทั้งสองไม่ตัดกัน ขอบที่จุดตัดจะถูกนับสองครั้ง นั่นคือ

${\displaystyle E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).}$

จากนั้นทฤษฎีบทการผสมตัวขยายกล่าวว่าอสมการต่อไปนี้เป็นจริง:

${\displaystyle \left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.}$

คุณสมบัติหลายประการของ กราฟ ( n , d , λ )เป็นผลลัพธ์จากทฤษฎีบทการผสมตัวขยาย ซึ่งรวมถึงสิ่งต่อไปนี้^{[ 1 ]}

• เซตอิสระของกราฟคือเซตย่อยของจุดยอดที่ไม่มีจุดยอดสองจุดใดอยู่ติดกัน ใน กราฟ ( n , d , λ )เซตอิสระจะมีขนาดไม่เกินλn / d
• จำนวนสีของกราฟG , χ ( G ) , คือจำนวนสีขั้นต่ำที่จำเป็นเพื่อให้จุดยอดที่อยู่ติดกันมีสีต่างกัน Hoffman แสดงให้เห็นว่าd ⁄ λ ≤ χ ( G ) , ^{[ 38 ]}ในขณะที่ Alon, Krivelevich และ Sudakov แสดงให้เห็นว่าถ้าd < 2 n ⁄ 3แล้ว^{[ 39 ]}

${\displaystyle \chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).}$

• เส้นผ่านศูนย์กลาง ของ กราฟคือระยะทางสูงสุดระหว่างจุดยอดสองจุด โดยระยะทางระหว่างจุดยอดสองจุดจะถูกกำหนดให้เป็นเส้นทางที่สั้นที่สุดระหว่างจุดยอดทั้งสอง Chung แสดงให้เห็นว่าเส้นผ่านศูนย์กลางของ กราฟ ( n , d , λ )มีค่าสูงสุด^{[ 40 ]}

${\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .}$

ขอบเขตของ เชอร์นอฟ ระบุว่า เมื่อสุ่มตัวอย่างอิสระจำนวนมากจากตัวแปรสุ่มในช่วง[−1, 1]ค่าเฉลี่ยของตัวอย่างจะใกล้เคียงกับค่าคาดหวังของตัวแปรสุ่มด้วยความน่าจะเป็นสูง ทฤษฎีบทการสุ่มตัวอย่างจากการเดินแบบขยาย (expander walk sampling lemma) ซึ่งพัฒนาโดยAjtai, Komlós & Szemerédi (1987)และGillman (1998)ระบุว่า สิ่งนี้ยังคงเป็นจริงเมื่อสุ่มตัวอย่างจากการเดินบนกราฟขยาย (expander graph) ซึ่งมีประโยชน์อย่างยิ่งในทฤษฎีการลดความสุ่ม (derandomization theory ) เนื่องจาก การสุ่มตัวอย่างตามการเดินแบบขยายใช้บิตสุ่มน้อยกว่าการสุ่มตัวอย่างแบบอิสระมาก

เครือข่ายการเรียงลำดับรับชุดข้อมูลอินพุตและดำเนินการตามขั้นตอนคู่ขนานหลายขั้นตอนเพื่อเรียงลำดับข้อมูลอินพุต ขั้นตอนคู่ขนานประกอบด้วยการเปรียบเทียบที่ไม่ซ้ำกันจำนวนเท่าใดก็ได้ และอาจสลับคู่ของข้อมูลอินพุตที่เปรียบเทียบกัน ความลึกของเครือข่ายกำหนดโดยจำนวนขั้นตอนคู่ขนานที่ดำเนินการ กราฟขยายมีบทบาทสำคัญในเครือข่ายการเรียงลำดับ AKS ซึ่งมีความลึกO (log n )แม้ว่านี่จะเป็นความลึกที่ดีที่สุดที่ทราบในเชิงอะซิมโทติกสำหรับเครือข่ายการเรียงลำดับ แต่การพึ่งพากราฟขยายทำให้ค่าคงที่ขอบเขตมีขนาดใหญ่เกินไปสำหรับการใช้งานจริง

ภายในเครือข่ายการเรียงลำดับ AKS กราฟขยายถูกใช้เพื่อสร้างตัวแบ่ง ครึ่ง ε ที่มีความลึกจำกัด ตัวแบ่งครึ่ง εรับอินพุตเป็นการเรียงสับเปลี่ยนความยาวnของ(1, …, n )และแบ่งอินพุตออกเป็นสองเซตที่ไม่ซ้ำกันAและBโดยที่สำหรับจำนวนเต็มk แต่ละตัว ≤ n ⁄ 2จะมีอินพุตที่เล็กที่สุดไม่เกินεkตัวในเซตB และมี อินพุต ที่ใหญ่ที่สุด ไม่เกินεkตัวใน เซต AเซตAและBเป็นตัวแบ่งครึ่ง ε

ตามAjtai, Komlós & Szemerédi (1983) สามารถสร้าง ε -halver ที่มีความลึกd ได้ดังนี้ พิจารณา ตัวขยายแบบทวิภาคที่มี nจุดยอดและดีกรีdโดยมีส่วนXและYที่มีขนาดเท่ากัน โดยที่เซตย่อยของจุดยอดทุกเซตที่มีขนาดไม่เกินεnจะมีอย่างน้อย⁠1 – ε/εเพื่อนบ้าน​

จุดยอดของกราฟเปรียบได้กับรีจิสเตอร์ที่เก็บอินพุต และขอบเปรียบได้กับสายไฟที่เปรียบเทียบอินพุตของรีจิสเตอร์สองตัว ในตอนเริ่มต้น ให้วางอินพุตครึ่งหนึ่งไว้ในXและอีกครึ่งหนึ่งไว้ในY โดยพลการ แล้วแยกขอบออกเป็นdคู่ที่จับคู่กันได้อย่างสมบูรณ์ เป้าหมายคือการทำให้Xมีอินพุตครึ่งหนึ่งที่เล็กกว่า และYมีอินพุตครึ่งหนึ่งที่ใหญ่กว่า เพื่อให้บรรลุเป้าหมายนี้ ให้ประมวลผลแต่ละคู่ที่จับคู่กันโดยการเปรียบเทียบรีจิสเตอร์ที่จับคู่กันด้วยขอบของคู่ที่จับคู่กัน และแก้ไขอินพุตใดๆ ที่ผิดลำดับ โดยเฉพาะอย่างยิ่ง สำหรับแต่ละขอบของคู่ที่จับคู่กัน หากอินพุตที่ใหญ่กว่าอยู่ในรีจิสเตอร์ในXและอินพุตที่เล็กกว่าอยู่ในรีจิสเตอร์ในYให้สลับอินพุตทั้งสองเพื่อให้ตัวที่เล็กกว่าอยู่ในXและตัวที่ใหญ่กว่าอยู่ในYเห็นได้ชัดว่ากระบวนการนี้ประกอบด้วยขั้นตอนขนาน d ขั้นตอน

หลังจากครบdรอบแล้ว ให้ถือว่าAเป็นเซตของอินพุตในรีจิสเตอร์ในXและBเป็นเซตของอินพุตในรีจิสเตอร์ในYเพื่อให้ได้ การลดลงครึ่งหนึ่ง แบบ εเพื่อให้เห็นภาพนี้ โปรดสังเกตว่า หากรีจิสเตอร์uในXและvในYเชื่อมต่อกันด้วยขอบuvแล้ว หลังจากประมวลผลการจับคู่กับขอบนี้แล้ว อินพุตในuจะน้อยกว่าอินพุตในvยิ่งไปกว่านั้น คุณสมบัตินี้ยังคงเป็นจริงตลอดกระบวนการที่เหลือ ทีนี้ สมมติว่าสำหรับk ≤ n ⁄ 2 บาง ค่า อินพุต(1, …, k )มากกว่าεk ตัวอยู่ในBแล้วโดยคุณสมบัติการขยายของกราฟ รีจิสเตอร์ของอินพุตเหล่านี้ในYจะเชื่อมต่อกันด้วยอย่างน้อย⁠1 – ε/εมี รีจิสเตอร์ kตัวใน Xโดยรวมแล้วมีจำนวนรีจิสเตอร์มากกว่า kตัว ดังนั้นจึงต้องมีรีจิสเตอร์ A บางตัว ใน Xที่เชื่อมต่อกับรีจิสเตอร์ B บางตัว ใน Yโดยที่อินพุตสุดท้ายของ Aไม่อยู่ใน (1, …, k )ในขณะที่อินพุตสุดท้ายของ B อยู่ใน (1, …, k ) อย่างไรก็ตาม สิ่งนี้ขัดแย้งกับคุณสมบัติก่อนหน้านี้ ดังนั้นชุดเอาต์พุต Aและ Bจึงต้องเป็นการหารครึ่ง แบบ ε

• การเชื่อมต่อเชิงพีชคณิต
• ผลิตภัณฑ์ซิกแซก
• การประมาณค่าที่แข็งแกร่งมาก
• ทฤษฎีกราฟสเปกตรัม

• Alexander, Clark (2021). "เกี่ยวกับกราฟขยายสเปกตรัมที่ใกล้เคียงค่าเหมาะสมที่สุดที่มีขนาดคงที่". arXiv : 2110.01407 [ cs.DM ].

• บทนำโดยย่อในวารสาร Notices of the American Mathematical Society
• บทความเบื้องต้นโดยไมเคิล นีลเซนเก็บรักษาไว้เมื่อวันที่ 17 สิงหาคม 2559 ที่Wayback Machine
• บันทึกการบรรยายจากหลักสูตรเกี่ยวกับเครื่องขยาย (โดย Nati Linial และ Avi Wigderson)
• บันทึกการบรรยายจากหลักสูตรเกี่ยวกับเครื่องขยาย (โดย ปราห์ลาธ ฮาร์ชา)
• นิยามและการประยุกต์ใช้ช่องว่างสเปกตรัม