ในทฤษฎีกราฟกราฟจะถูกเรียกว่ากราฟสุ่มเทียม (pseudorandom graph)หากกราฟนั้นมีคุณสมบัติบางอย่างที่กราฟสุ่มทั่วไปมีด้วยความน่าจะเป็นสูงไม่มีคำจำกัดความที่ตายตัวสำหรับความเป็นกราฟสุ่ม เทียม แต่มีลักษณะเฉพาะของความเป็นกราฟสุ่มเทียมที่สมเหตุสมผลหลายอย่างที่สามารถนำมาพิจารณาได้

คุณสมบัติแบบสุ่มเทียมได้รับการพิจารณาอย่างเป็นทางการครั้งแรกโดย Andrew Thomason ในปี 1987 ^{[ 1 ] [ 2 ]}เขาได้กำหนดเงื่อนไขที่เรียกว่า "ความยุ่งเหยิง": กราฟจะถูกกล่าวว่ายุ่งเหยิงทั้งในความเป็นจริงและด้วยเงื่อนไข ${\displaystyle G=(V,E)}$${\displaystyle (p,\alpha )}$${\displaystyle p}$${\displaystyle \alpha }$${\displaystyle 0<p<1\leq \alpha }$

${\displaystyle \left|e(U)-p{\binom {|U|}{2}}\right|\leq \alpha |U|}$

สำหรับทุกเซตย่อยของเซตจุดยอดโดยที่คือจำนวนขอบระหว่าง(หรือเทียบเท่ากับจำนวนขอบในกราฟย่อยที่เกิดจากเซตจุดยอด) สามารถแสดงได้ว่ากราฟสุ่มErdős–Rényi เกือบจะสุ่มแบบ -jumbled [ ^{2 ] : 6} อย่างไรก็ตาม กราฟที่มีขอบกระจายไม่สม่ำเสมอ เช่น กราฟบนจุดยอดที่ประกอบด้วยกราฟสมบูรณ์ -จุด ยอด และจุดยอดอิสระโดยสมบูรณ์ จะไม่สุ่มแบบ -jumbled สำหรับค่าเล็กๆ ใดๆทำให้ความสุ่มเป็นตัวบ่งชี้ที่เหมาะสมสำหรับคุณสมบัติ "คล้ายสุ่ม" ของการกระจายขอบของกราฟ ${\displaystyle U}$${\displaystyle V}$${\displaystyle e(U)}$${\displaystyle U}$${\displaystyle U}$${\displaystyle G(n,p)}$${\displaystyle (p,O({\sqrt {np}}))}}$${\displaystyle 2n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle (p,\alpha )}$${\displaystyle \alpha }$

Thomason แสดงให้เห็นว่าเงื่อนไข "สับสน" นั้นบ่งบอกโดยเงื่อนไขที่ตรวจสอบได้ง่ายกว่า โดยขึ้นอยู่กับโคดีกรีของจุดยอดสองจุดเท่านั้น ไม่ใช่ทุกเซตย่อยของเซตจุดยอดของกราฟ ให้เป็นจำนวนเพื่อนบ้านร่วมของจุดยอดสองจุดและThomason แสดงให้เห็นว่า เมื่อกำหนดกราฟที่มีจุดยอด n จุดและดีกรีต่ำสุดถ้าสำหรับทุกและแล้วจะเป็นกราฟที่สับสน^{[ 2 ] : 7} ผลลัพธ์นี้แสดงให้เห็นวิธีการตรวจสอบเงื่อนไขความสับสนด้วยอัลกอริทึมในเวลาพหุนามตามจำนวนจุดยอด และสามารถใช้เพื่อแสดงความสุ่มเทียมของกราฟเฉพาะได้^{[ 2 ] : 7} ${\displaystyle \ชื่อผู้ดำเนินการ {codeg} (u,v)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle G}$${\displaystyle n}$${\displaystyle np}$${\displaystyle \operatorname {codeg} (u,v)\leq np^{2}+\ell }$${\displaystyle u}$${\displaystyle v}$${\displaystyle G}$${\displaystyle \left(p,{\sqrt {(p+\ell )n}}\,\right)}$

ด้วยเจตนารมณ์ของเงื่อนไขที่ Thomason พิจารณาและลักษณะที่เป็นสากลและเฉพาะที่สลับกันไป Chung, Graham และ Wilson ได้พิจารณาเงื่อนไขที่อ่อนกว่าหลายประการในปี 1989: ^{[ 3 ]}กราฟบนจุดยอดที่มีความหนาแน่นของขอบและบางส่วนสามารถตอบสนองเงื่อนไขเหล่านี้ได้หาก ${\displaystyle G}$${\displaystyle n}$${\displaystyle p}$${\displaystyle \varepsilon >0}$

• ความคลาดเคลื่อน : สำหรับเซตย่อยใดๆของเซตจุดยอดจำนวนขอบระหว่างและจะอยู่ภายในช่วง${\displaystyle X,Y}$${\displaystyle V=V(G)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \varepsilon n^{2}}$${\displaystyle p|X||Y|}$
• ความคลาดเคลื่อนในแต่ละเซต : สำหรับเซตย่อยใดๆของจำนวนขอบระหว่างเซตย่อยนั้นจะอยู่ภายในช่วง${\displaystyle X}$${\displaystyle V}$${\displaystyle X}$${\displaystyle \varepsilon n^{2}}$${\displaystyle p{\binom {|X|}{2}}}$
• การนับซับกราฟ : สำหรับทุกกราฟจำนวนสำเนาที่มีป้ายกำกับของในบรรดาซับกราฟของจะอยู่ภายในช่วงของ${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$${\displaystyle \varepsilon n^{v(H)}}$${\displaystyle p^{e(H)}n^{v(H)}}$
• การนับแบบ 4 รอบ : จำนวนรอบที่มีป้ายกำกับในกลุ่มกราฟย่อยของอยู่ภายในช่วง${\displaystyle 4}$${\displaystyle G}$${\displaystyle \varepsilon n^{4}}$${\displaystyle p^{4}n^{4}}$
• โคดีกรี : ให้เป็นจำนวนเพื่อนบ้านร่วมกันของจุดยอดสองจุดและ,${\displaystyle \ชื่อผู้ดำเนินการ {codeg} (u,v)}$${\displaystyle u}$${\displaystyle v}$

${\displaystyle \sum _{u,v\in V}{\big |}\ชื่อผู้ดำเนินการ {codeg} (u,v)-p^{2}n{\big |}\leq \varepsilon n^{3}.}$

• การกำหนดขอบเขตค่าไอเกน : ถ้าและ คือค่าไอเกนของเมทริกซ์ประชิดของแล้วจะอยู่ภายในและของ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$${\displaystyle G}$${\displaystyle \lambda _{1}}$${\displaystyle \varepsilon n}$${\displaystyle pn}$${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \varepsilon n}$

เงื่อนไขเหล่านี้ทั้งหมดสามารถระบุได้ในรูปของลำดับของกราฟโดยที่อยู่บนจุดยอดที่มีขอบ ตัวอย่างเช่น เงื่อนไขการนับวัฏจักร 4 รอบ จะกลายเป็นว่าจำนวนสำเนาของกราฟใดๆในคือและเงื่อนไขความคลาดเคลื่อนจะกลายเป็นโดยใช้สัญกรณ์ little- o ${\displaystyle \{G_{n}\}}$${\displaystyle G_{n}}$${\displaystyle n}$${\displaystyle (p+o(1)){\binom {n}{2}}}$${\displaystyle H}$${\displaystyle G_{n}}$${\displaystyle \left(p^{e(H)}+o(1)\right)e^{v(H)}}$${\displaystyle n\to \infty }$${\displaystyle \left|e(X,Y)-p|X||Y|\right|=o(n^{2})}$

ผลลัพธ์สำคัญเกี่ยวกับความสุ่มเทียมของกราฟคือทฤษฎีบท Chung–Graham–Wilson ซึ่งระบุว่าเงื่อนไขข้างต้นหลายข้อเทียบเท่ากัน โดยมีการเปลี่ยนแปลงพหุนามใน^{[ 3 ]}ลำดับของกราฟที่ตรงตามเงื่อนไขเหล่านั้นเรียกว่ากราฟกึ่งสุ่มถือเป็นเรื่องที่น่าแปลกใจเป็นพิเศษ^{[ 2 ] : 9} ที่เงื่อนไขที่อ่อนแอของการมีความหนาแน่นของวงจร 4 วงที่ "ถูกต้อง" บ่งบอกถึงเงื่อนไขความสุ่มเทียมอื่นๆ ที่ดูเหมือนจะแข็งแกร่งกว่ามาก กราฟเช่นวงจร 4 วง ซึ่งความหนาแน่นในลำดับของกราฟเพียงพอที่จะทดสอบความสุ่มเทียมของลำดับนั้น เรียกว่ากราฟบังคับ ${\displaystyle \varepsilon }$

ข้อสรุปบางประการในทฤษฎีบทชุง-เกรแฮม-วิลสันนั้นชัดเจนจากคำจำกัดความของเงื่อนไขต่างๆ เช่น เงื่อนไขความคลาดเคลื่อนของเซตแต่ละเซตเป็นเพียงกรณีพิเศษของเงื่อนไขความคลาดเคลื่อนสำหรับและการนับวัฏจักร 4 รอบเป็นกรณีพิเศษของการนับกราฟย่อย นอกจากนี้ บทพิสูจน์การนับกราฟ ซึ่งเป็นการวางนัยทั่วไปโดยตรงของบทพิสูจน์การนับสามเหลี่ยมบ่งชี้ว่าเงื่อนไขความคลาดเคลื่อนนั้นหมายถึงการนับกราฟย่อยด้วย ${\displaystyle Y=X}$

ข้อเท็จจริงที่ว่าการนับแบบ 4 รอบบ่งชี้ถึงเงื่อนไขโคดีกรีนั้นสามารถพิสูจน์ได้ด้วยเทคนิคที่คล้ายกับวิธีโมเมนต์ที่สอง ขั้นแรก ผลรวมของโคดีกรีสามารถกำหนดขอบเขตบนได้:

${\displaystyle \sum _{u,v\in G}\operatorname {codeg} (u,v)=\sum _{x\in G}\deg(x)^{2}\geq n\left({\frac {2e(G)}{n}}\right)^{2}=\left(p^{2}+o(1)\right)n^{3}.}$

เมื่อกำหนดวัฏจักร 4 ตัว ผลรวมของกำลังสองของโคดีกรีจะมีค่าจำกัด:

${\displaystyle \sum _{u,v}\operatorname {codeg} (u,v)^{2}={\text{จำนวนสำเนาที่มีป้ายกำกับของ }}C_{4}+o(n^{4})\leq \left(p^{4}+o(1)\right)n^{4}.}$

ดังนั้นอสมการโคชี-ชวาร์ซจึงให้ผลลัพธ์ ดังนี้

${\displaystyle \sum _{u,v\in G}|\operatorname {codeg} (u,v)-p^{2}n|\leq n\left(\sum _{u,v\in G}\left(\operatorname {codeg} (u,v)-p^{2}n\right)^{2}\right)^{1/2},}$

ซึ่งสามารถขยายออกไปได้โดยใช้ขอบเขตของเราเกี่ยวกับโมเมนต์แรกและโมเมนต์ที่สองของเพื่อให้ได้ขอบเขตที่ต้องการ การพิสูจน์ว่าเงื่อนไขโคดีกรีบ่งชี้ถึงเงื่อนไขความคลาดเคลื่อน สามารถทำได้โดยการคำนวณที่คล้ายกัน แต่ซับซ้อนกว่า ซึ่งเกี่ยวข้องกับอสมการโคชี-ชวาร์ซ ${\displaystyle \ชื่อผู้ดำเนินการ {codeg} }$

เงื่อนไขค่าลักษณะเฉพาะและเงื่อนไข 4-ไซเคิลสามารถเชื่อมโยงกันได้โดยการสังเกตว่าจำนวน 4-ไซเคิลที่มีป้ายกำกับในคือ โดยที่คือเมทริกซ์ประชิดของจากนั้นสามารถแสดงให้เห็นว่าเงื่อนไขทั้งสองเทียบเท่ากันได้โดยการอ้างถึงทฤษฎีบทCourant–Fischer ^{[ 3 ]}${\displaystyle G}$${\displaystyle o(1)}$${\displaystyle \operatorname {tr} \left(A_{G}^{4}\right)}$${\displaystyle A_{G}}$${\displaystyle G}$

แนวคิดของกราฟที่ทำหน้าที่เหมือนกราฟสุ่มมีความเชื่อมโยงอย่างแน่นหนากับแนวคิดของความสม่ำเสมอของกราฟที่ใช้ในบทพิสูจน์ความสม่ำเสมอของ Szemerédiสำหรับคู่ของเซตจุดยอดเรียกว่า-สม่ำเสมอถ้าสำหรับทุกเซตย่อยที่สอดคล้องกับ จะเป็นจริงว่า ${\displaystyle \varepsilon >0}$${\displaystyle X,Y}$${\displaystyle \varepsilon }$${\displaystyle A\subset X,B\subset Y}$${\displaystyle |A|\geq \varepsilon |X|,|B|\geq \varepsilon |Y|}$

${\displaystyle \left|d(X,Y)-d(A,B)\right|\leq \varepsilon ,}$

โดยที่หมายถึงความหนาแน่นของขอบระหว่างและ: จำนวนขอบระหว่างและหารด้วยเงื่อนไขนี้บ่งบอกถึงอนาล็อกแบบทวิภาคของเงื่อนไขความคลาดเคลื่อน และโดยพื้นฐานแล้วระบุว่าขอบระหว่างและมีพฤติกรรมในลักษณะ "คล้ายสุ่ม" นอกจากนี้Miklós SimonovitsและVera T. Sós ได้แสดงให้เห็น ในปี 1991 ว่ากราฟจะตรงตามเงื่อนไขความสุ่มเทียมแบบอ่อนข้างต้นที่ใช้ในทฤษฎีบท Chung–Graham–Wilson ก็ต่อเมื่อมีพาร์ทิชัน Szemerédi ซึ่งความหนาแน่นเกือบทั้งหมดใกล้เคียงกับความหนาแน่นของขอบของกราฟทั้งหมด^{[ 4 ]}${\displaystyle d(X,Y)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle |X||Y|}$${\displaystyle A}$${\displaystyle B}$

ทฤษฎีบทชุง-เกรแฮม-วิลสัน โดยเฉพาะอย่างยิ่งข้อสรุปของการนับกราฟย่อยจากความคลาดเคลื่อน ไม่เป็นจริงสำหรับลำดับของกราฟที่มีความหนาแน่นของขอบเข้าใกล้หรือตัวอย่างเช่น กรณีทั่วไปของ กราฟ ปกติบนจุดยอดเมื่อเงื่อนไขขอบเขตความคลาดเคลื่อนและค่าลักษณะเฉพาะที่คล้ายคลึงกันแบบเบาบางต่อไปนี้มักถูกนำมาพิจารณา: ${\displaystyle 0}$${\displaystyle d}$${\displaystyle n}$${\displaystyle n\to \infty }$

• ความคลาดเคลื่อนแบบเบาบาง : สำหรับเซตย่อยใดๆของเซตจุดยอดจำนวนขอบระหว่างและจะอยู่ภายในช่วง${\displaystyle X,Y}$${\displaystyle V=V(G)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \varepsilon dn}$${\displaystyle {\frac {d}{n}}|X||Y|}$
• การกำหนดขอบเขตค่าไอเกนแบบเบาบาง : ถ้าคือค่าไอเกนของเมทริกซ์ประชิดของแล้ว.${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$${\displaystyle G}$${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \varepsilon d}$

โดยทั่วไปแล้ว เงื่อนไขค่าลักษณะเฉพาะนี้บ่งชี้ถึงเงื่อนไขความคลาดเคลื่อนที่สอดคล้องกัน แต่ในทางกลับกันนั้นไม่เป็นจริง: การรวมกันแบบไม่ทับซ้อนกันของกราฟขนาดใหญ่แบบสุ่มที่มี -regular และกราฟสมบูรณ์ที่มี -vertex จะมีค่าลักษณะเฉพาะสองค่าเท่ากับแต่มีแนวโน้มที่จะเป็นไปตามคุณสมบัติความคลาดเคลื่อน อย่างไรก็ตาม ดังที่พิสูจน์โดยDavid Conlonและ Yufei Zhao ในปี 2017 ตัวแปรเล็กน้อยของเงื่อนไขความคลาดเคลื่อนและค่าลักษณะเฉพาะสำหรับกราฟ Cayleyที่มี -regular นั้นเทียบเท่ากันจนถึงการปรับขนาดเชิงเส้นใน[ ^{5 ] ทิศทาง}หนึ่งของสิ่งนี้เป็นไปตามเลมมาการผสมตัวขยายในขณะที่อีกทิศทางหนึ่งต้องอาศัยสมมติฐานว่ากราฟเป็นกราฟ Cayley และใช้ความไม่เท่าเทียมกันของ Grothendieck ${\displaystyle d}$${\displaystyle d+1}$${\displaystyle d}$${\displaystyle d}$${\displaystyle \varepsilon }$

กราฟปกติบนจุดยอดเรียกว่ากราฟถ้าให้ค่าลักษณะเฉพาะของเมทริกซ์ประชิดของเป็นขอบเขตAlon -Boppanaให้ว่า(โดยที่เทอมเป็น) และ Joel Friedman พิสูจน์ว่ากราฟปกติแบบสุ่มบนจุดยอดคือสำหรับ^{[ 6} ] ในแง่นี้ ปริมาณของที่เกินเป็นมาตรวัดทั่วไปของความไม่สุ่มของกราฟ มีกราฟที่มีซึ่งเรียกว่ากราฟ Ramanujan กราฟเหล่านี้ได้รับการศึกษาอย่างกว้างขวางและมีปัญหาเปิดจำนวนหนึ่งที่ ^{เกี่ยวข้อง}กับการมีอยู่และความแพร่หลายของกราฟเหล่านี้ ${\displaystyle d}$${\displaystyle G}$${\displaystyle n}$${\displaystyle (n,d,\lambda )}$${\displaystyle G}$${\displaystyle d=\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \lambda }$${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\geq 2{\sqrt {d-1}}-o(1)}$${\displaystyle o(1)}$${\displaystyle n\to \infty }$${\displaystyle d}$${\displaystyle n}$${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda =2{\sqrt {d-1}}+o(1)}$${\displaystyle \lambda }$${\displaystyle 2{\sqrt {d-1}}}$${\displaystyle \lambda \leq 2{\sqrt {d-1}}}$

เมื่อกำหนดกราฟสำหรับค่า n ขนาดเล็กปริมาณทางทฤษฎีกราฟมาตรฐานหลายอย่างสามารถจำกัดให้ใกล้เคียงกับสิ่งที่คาดหวังได้จากกราฟสุ่ม โดยเฉพาะอย่างยิ่ง ขนาดของ n มีผลโดยตรงต่อความคลาดเคลื่อนของความหนาแน่นของขอบในเซตย่อยผ่านทฤษฎีบทการผสมตัวขยาย ตัวอย่างอื่นๆ มีดังต่อไปนี้ โดยให้ n เป็นกราฟ: ${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda }$${\displaystyle \lambda }$${\displaystyle G}$${\displaystyle (n,d,\lambda )}$

• ถ้าการเชื่อมต่อจุดยอดเป็นไปตาม^{[ 7 ]}${\displaystyle d\leq {\frac {n}{2}}}$${\displaystyle \kappa (G)}$${\displaystyle G}$${\displaystyle \kappa (G)\geq d-{\frac {36\lambda ^{2}}{d}}.}$
• ถ้าเป็นเส้นเชื่อมขอบถ้าเป็นเลขคู่จะมีการจับคู่ที่สมบูรณ์แบบ^{[ 2 ] : 32} ${\displaystyle \lambda \leq d-2}$${\displaystyle G}$${\displaystyle d}$${\displaystyle n}$${\displaystyle G}$
• การตัดสูงสุดคือไม่เกิน. ^{[ 2 ] : 33} ${\displaystyle G}$${\displaystyle {\frac {n(d+\lambda )}{4}}}$
• เซตย่อยอิสระที่ใหญ่ที่สุดของเซตย่อยในมีขนาดอย่างน้อย^{[ 8 ]}${\displaystyle U\subset V(G)}$${\displaystyle G}$${\displaystyle {\frac {n}{2(d-\lambda )}}\ln \left({\frac {|U|(d-\lambda )}{n(\lambda +1)}}+1\right).}$
• จำนวนสีที่มากที่สุดคือ^{[ 8 ]}${\displaystyle G}$${\displaystyle {\frac {6(d-\lambda )}{\ln \left({\frac {d+1}{\lambda +1}}\right)}}.}$

กราฟสุ่มเทียมมีบทบาทสำคัญในการพิสูจน์ทฤษฎีบทกรีน-เทาทฤษฎีบทนี้ได้รับการพิสูจน์โดยการถ่ายโอนทฤษฎีบทของเซเมอเรดีซึ่งเป็นข้อความที่ว่าเซตของจำนวนเต็มบวกที่มีความหนาแน่นตามธรรมชาติ เป็นบวก ประกอบด้วยลำดับเลขคณิตที่ยาวตามอำเภอใจ ไปยังการตั้งค่าแบบเบาบาง (เนื่องจากจำนวนเฉพาะมีความหนาแน่นตามธรรมชาติในจำนวนเต็ม) การถ่ายโอนไปยังเซตแบบเบาบางต้องการให้เซตเหล่านั้นมีพฤติกรรมแบบสุ่มเทียม ในแง่ที่ว่ากราฟและไฮเปอร์กราฟที่สอดคล้องกันมีความหนาแน่นของกราฟย่อยที่ถูกต้องสำหรับเซตของกราฟย่อย (ไฮเปอร์) ขนาดเล็กที่กำหนดไว้^{[ 9 ]}จากนั้นจึงแสดงให้เห็นว่าซูเปอร์เซตที่เหมาะสมของจำนวนเฉพาะที่เรียกว่าจำนวนเฉพาะเทียม ซึ่งจำนวนเฉพาะมีความหนาแน่นนั้นเป็นไปตามเงื่อนไขความสุ่มเทียมเหล่านี้ ทำให้การพิสูจน์เสร็จสมบูรณ์ ${\displaystyle 0}$