ในทฤษฎีกราฟและสถิติกราฟอน (หรือที่เรียกว่าลิมิตของกราฟ ) คือฟังก์ชันสมมาตรที่วัด ได้ ซึ่งมีความสำคัญในการศึกษากราฟหนาแน่นกราฟอนเกิดขึ้นทั้งในฐานะแนวคิดตามธรรมชาติสำหรับลิมิตของลำดับของกราฟหนาแน่น และในฐานะวัตถุพื้นฐานที่กำหนด แบบจำลองกราฟสุ่ม ที่แลกเปลี่ยนได้กราฟอนมีความเชื่อมโยงกับกราฟหนาแน่นโดยข้อสังเกตสองประการต่อไปนี้: แบบจำลองกราฟสุ่มที่กำหนดโดยกราฟอนก่อให้เกิดกราฟหนาแน่นเกือบแน่นอนและโดยทฤษฎีบทความสม่ำเสมอกราฟอนสามารถจับโครงสร้างของกราฟหนาแน่นขนาดใหญ่ใดๆ ได้ ${\displaystyle W:[0,1]^{2}\ถึง [0,1]}$

กราฟอน (Graphon) คือฟังก์ชันสมมาตรที่วัดได้โดยปกติแล้ว กราฟอนจะถูกเข้าใจว่าเป็นการกำหนดแบบจำลองกราฟสุ่มที่แลกเปลี่ยนได้ตามแผนผังต่อไปนี้: ${\displaystyle W:[0,1]^{2}\ถึง [0,1]}$

1. แต่ละจุดยอดของกราฟจะได้รับค่าสุ่มอิสระ${\displaystyle j}$${\displaystyle u_{j}\sim U[0,1]}$
2. เส้นเชื่อมจะถูกรวมอยู่ในกราฟโดยอิสระด้วยความน่าจะเป็น.${\displaystyle (i,j)}$${\displaystyle W(u_{i},u_{j})}$

แบบจำลองกราฟสุ่มจะเป็นแบบจำลองกราฟสุ่มที่แลกเปลี่ยนได้ก็ต่อเมื่อสามารถนิยามได้ในรูปของกราฟอน (ซึ่งอาจเป็นแบบสุ่ม) ในลักษณะนี้ แบบจำลองที่อิงตามกราฟอนคงที่บางครั้งจะถูกแทนด้วยโดยเปรียบเทียบกับ แบบจำลองกราฟสุ่มของ Erdős–Rényiกราฟที่สร้างขึ้นจากกราฟอนในลักษณะนี้เรียกว่ากราฟสุ่ม ${\displaystyle W}$${\displaystyle \mathbb {G} (n,W)}$${\displaystyle W}$${\displaystyle W}$

จากคำจำกัดความนี้และ กฎของจำนวนมากจึงสรุปได้ว่า ถ้าแบบจำลองกราฟสุ่มที่แลกเปลี่ยนได้จะมีความหนาแน่นเกือบแน่นอน^{[ 1 ]}${\displaystyle W\neq 0}$

ตัวอย่างที่ง่ายที่สุดของกราฟอนคือสำหรับค่าคงที่บางค่าในกรณีนี้ แบบจำลองกราฟสุ่มที่แลกเปลี่ยนได้ที่เกี่ยวข้องคือแบบจำลองErdős–Rényiซึ่งรวมขอบแต่ละขอบอย่างอิสระด้วยความน่าจะเป็น ${\displaystyle W(x,y)\equiv p}$${\displaystyle p\in [0,1]}$${\displaystyle G(n,p)}$${\displaystyle p}$

หากเราเริ่มต้นด้วยกราฟอนที่มีค่าคงที่แบบเป็นช่วงๆ ดังนี้:

1. โดยการแบ่งพื้นที่สี่เหลี่ยมจัตุรัสหน่วยออกเป็นช่อง ๆ และ${\displaystyle k\times k}$
2. ตั้งค่าให้เท่ากับบนบล็อก${\displaystyle W}$${\displaystyle p_{lm}}$${\displaystyle (\ell ,m)^{\text{th}}}$

แบบจำลองกราฟสุ่มที่แลกเปลี่ยนได้ซึ่งเป็นผลลัพธ์นี้คือแบบจำลองบล็อกสุ่ม ชุมชนซึ่งเป็นการขยายความของแบบจำลอง Erdős–Rényi เราสามารถตีความได้ว่าเป็นแบบจำลองกราฟสุ่มที่ประกอบด้วยกราฟ Erdős–Rényi ที่แตกต่างกัน โดยมีพารามิเตอร์ตามลำดับ และมีบิกราฟระหว่างกัน โดยที่ขอบที่เป็นไปได้แต่ละขอบระหว่างบล็อกจะถูกรวมไว้โดยอิสระด้วยความน่าจะเป็น ${\displaystyle k}$${\displaystyle k}$${\displaystyle p_{\ell \ell }}$${\displaystyle (\ell ,\ell )}$${\displaystyle (m,m)}$${\displaystyle p_{\ell m}}$

แบบจำลองกราฟสุ่มยอดนิยมอื่นๆ อีกมากมายสามารถเข้าใจได้ว่าเป็นแบบจำลองกราฟสุ่มที่แลกเปลี่ยนได้ซึ่งกำหนดโดยกราฟอนบางประเภท การสำรวจโดยละเอียดรวมอยู่ใน Orbanz และ Roy ^{[ 1 ]}

กราฟสุ่มที่มีขนาดสามารถแสดงได้ด้วยเมทริกซ์ประชิด สุ่ม เพื่อให้เกิดความสอดคล้อง (ในแง่ของความเป็นโปรเจคทีฟ ) ระหว่างกราฟสุ่มที่มีขนาดต่างกัน จึงเป็นเรื่องธรรมชาติที่จะศึกษาลำดับของเมทริกซ์ประชิดที่เกิดขึ้นจากเมทริกซ์ย่อยด้านบนซ้ายของอาร์เรย์อนันต์ของตัวแปรสุ่ม ซึ่งทำให้เราสามารถสร้างโดยการเพิ่มโหนดลงในและสุ่มเลือกขอบสำหรับ ด้วยมุมมองนี้ กราฟสุ่มจึงถูกนิยามว่าเป็นอาร์เรย์สมมาตร อนันต์ แบบสุ่ม${\displaystyle n}$${\displaystyle n\times n}$${\displaystyle n\times n}$${\displaystyle G_{n}}$${\displaystyle G_{n-1}}$${\displaystyle (j,n)}$${\displaystyle j<n}$${\displaystyle (X_{ij})}$

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

${\displaystyle (X_{ij})\ {\overset {d}{=}}\,(X_{\sigma (i)\sigma (j)})}$

สำหรับการเรียงสับเปลี่ยนทั้งหมดของจำนวนธรรมชาติ โดยที่หมายถึงการกระจายที่เท่ากันโดยสัญชาตญาณแล้ว เงื่อนไขนี้หมายความว่าการกระจายของกราฟสุ่มจะไม่เปลี่ยนแปลงไปเมื่อมีการกำหนดป้ายกำกับใหม่ให้กับจุดยอด: กล่าวคือ ป้ายกำกับของจุดยอดไม่ได้ให้ข้อมูลใดๆ ${\displaystyle \sigma }$${\displaystyle {\overset {d}{=}}}$

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

1. สุ่มตัวอย่างอย่างอิสระ${\displaystyle u_{j}\sim U[0,1]}$
2. ${\displaystyle X_{ij}=X_{ji}=1}$โดยอิสระแบบสุ่มด้วยความน่าจะเป็น${\displaystyle W(u_{i},u_{j}),}$

โดยที่เป็นกราฟอน (ซึ่งอาจเป็นแบบสุ่ม) กล่าวคือ แบบจำลองกราฟแบบสุ่มจะมีเมทริกซ์ประชิดที่แลกเปลี่ยนร่วมกันได้ก็ต่อเมื่อเป็นแบบจำลองกราฟแบบสุ่มที่แลกเปลี่ยนร่วมกันได้ ซึ่งกำหนดขึ้นโดยใช้กราฟอนบางตัว ${\displaystyle W:[0,1]^{2}\ถึง [0,1]}$

เนื่องจากปัญหาการระบุตัวตน จึงเป็นไปไม่ได้ที่จะประมาณฟังก์ชันกราฟอนหรือตำแหน่งแฝงของโหนดและมีทิศทางหลักสองทิศทางในการประมาณกราฟอน ทิศทางหนึ่งมุ่งเป้าไปที่การประมาณจนถึงชั้นสมมูล^{[ 2 ] [ 3 ]}หรือประมาณเมทริกซ์ความน่าจะเป็นที่เกิดจาก^{[ 4 ] [ 5 ]}${\displaystyle W}$${\displaystyle u_{i},}$${\displaystyle W}$${\displaystyle W}$

กราฟใดๆ ที่มีจุดยอด n จุดสามารถระบุได้ด้วยเมทริกซ์ประชิดเมทริกซ์นี้สอดคล้องกับฟังก์ชันขั้นบันไดซึ่งกำหนดโดยการแบ่งช่วงออกเป็นช่วงๆ โดยที่มีค่าภายใน เท่ากับ และสำหรับแต่ละช่วงให้กำหนดค่าเท่ากับ ค่าในเมทริกซ์ฟังก์ชันนี้คือกราฟอนที่เกี่ยวข้องกับกราฟนั้น ${\displaystyle n}$${\displaystyle \{1,2,\dots ,n\}}$${\displaystyle A_{G}}$${\displaystyle W_{G}:[0,1]^{2}\ถึง [0,1]}$${\displaystyle [0,1]}$${\displaystyle I_{1},I_{2},\dots ,I_{n}}$${\displaystyle I_{j}}$$${\displaystyle \left({\frac {j-1}{n}},{\frac {j}{n}}\right)}$$${\displaystyle (x,y)\in I_{i}\times I_{j}}$${\displaystyle W_{G}(x,y)}$${\displaystyle (i,j)^{\text{th}}}$${\displaystyle A_{G}}$${\displaystyle W_{G}}$${\displaystyle G}$

โดยทั่วไป ถ้าเรามีลำดับของกราฟที่จำนวนจุดยอดมีค่าเข้าสู่ค่าอนันต์ เราสามารถวิเคราะห์พฤติกรรมลิมิตของลำดับนั้นได้โดยพิจารณาจากพฤติกรรมลิมิตของฟังก์ชันต่างๆถ้ากราฟเหล่านี้ลู่เข้า (ตามนิยามการลู่เข้า ที่เหมาะสม ) เราคาดว่าลิมิตของกราฟเหล่านี้จะสอดคล้องกับลิมิตของฟังก์ชันที่เกี่ยวข้องเหล่านั้น ${\displaystyle (G_{n})}$${\displaystyle G_{n}}$${\displaystyle (W_{G_{n}})}$

สิ่งนี้กระตุ้นให้เกิดการนิยามกราฟอน (ย่อมาจาก "ฟังก์ชันกราฟ") ว่าเป็นฟังก์ชันที่วัดได้สมมาตรซึ่งจับแนวคิดของลิมิตของลำดับกราฟ ปรากฏว่าสำหรับลำดับของกราฟหนาแน่น แนวคิดของการลู่เข้าที่ดูเหมือนแตกต่างกันหลายอย่างนั้นเทียบเท่ากัน และภายใต้แนวคิดทั้งหมดนั้น วัตถุลิมิตตามธรรมชาติคือกราฟอน^{[ 6 ]}${\displaystyle W:[0,1]^{2}\to [0,1]}$

พิจารณาลำดับของกราฟสุ่ม Erdős–Rényi ที่มีพารามิเตอร์คงที่ค่าหนึ่ง โดยสัญชาตญาณแล้ว เมื่อเข้าใกล้ค่าอนันต์ ลิมิตของลำดับกราฟนี้จะถูกกำหนดโดยความหนาแน่นของขอบของกราฟเหล่านั้นเพียงอย่างเดียว ในปริภูมิของกราฟอน ปรากฏว่าลำดับดังกล่าวลู่เข้าสู่ค่าคงที่เกือบแน่นอนซึ่งสอดคล้องกับสัญชาตญาณข้างต้น ${\displaystyle (G_{n})}$${\displaystyle G_{n}=G(n,p)}$${\displaystyle p}$${\displaystyle n}$${\displaystyle W(x,y)\equiv p}$

พิจารณาลำดับของกราฟครึ่งส่วนซึ่งกำหนดโดยการให้เป็นกราฟสองส่วนที่มีจุดยอดและโดยที่จะอยู่ติดกับ ก็ต่อเมื่อ เท่านั้นหากจุดยอดถูกเรียงลำดับตามที่แสดง เมทริกซ์ประชิดจะมีมุมสองมุมเป็นเมทริกซ์บล็อก "ครึ่งสี่เหลี่ยม" ที่เต็มไปด้วยเลขหนึ่ง โดยที่ค่าที่เหลือเท่ากับศูนย์ ตัวอย่างเช่น เมทริกซ์ประชิดของจะกำหนดโดย ${\displaystyle (H_{n})}$${\displaystyle H_{n}}$${\displaystyle 2n}$${\displaystyle u_{1},u_{2},\dots ,u_{n}}$${\displaystyle v_{1},v_{2},\dots ,v_{n}}$${\displaystyle u_{i}}$${\displaystyle v_{j}}$${\displaystyle i\leq j}$${\displaystyle A_{H_{n}}}$${\displaystyle H_{3}}$

$${\displaystyle {\begin{bmatrix}0&0&0&1&1&1\\0&0&0&0&1&1\\0&0&0&0&0&1\\1&0&0&0&0&0\\1&1&0&0&0&0\\1&1&1&0&0&0\end{bmatrix}}.}$$

เมื่อค่ามีขนาดใหญ่ขึ้น มุมเหล่านี้จะ "เรียบเนียน" ขึ้น สอดคล้องกับสัญชาตญาณนี้ ลำดับจะลู่เข้าสู่ครึ่งกราฟที่กำหนดโดยเงื่อนไขเมื่อและในกรณีอื่น ๆ ${\displaystyle n}$${\displaystyle (H_{n})}$${\displaystyle W}$${\displaystyle W(x,y)=1}$${\displaystyle |x-y|\geq 1/2}$${\displaystyle W(x,y)=0}$

พิจารณาลำดับของกราฟสองส่วนสมบูรณ์ที่มีส่วนขนาดเท่ากัน ถ้าเราเรียงลำดับจุดยอดโดยวางจุดยอดทั้งหมดของส่วนหนึ่งไว้ที่จุดเริ่มต้นและวางจุดยอดของอีกส่วนหนึ่งไว้ที่จุดสิ้นสุด เมทริกซ์ประชิดของกราฟจะมีลักษณะเป็นเมทริกซ์นอกแนวทแยงมุมแบบบล็อก โดยมีบล็อกของเลขหนึ่งสองบล็อกและบล็อกของเลขศูนย์สองบล็อก ตัวอย่างเช่น เมทริกซ์ประชิดของกราฟจะมีค่าดังนี้ ${\displaystyle (K_{n,n})}$${\displaystyle (K_{n,n})}$${\displaystyle K_{2,2}}$

$${\displaystyle {\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.}$$

เมื่อมีขนาดใหญ่ขึ้น โครงสร้างบล็อกของเมทริกซ์ประชิดจะยังคงที่ ดังนั้นลำดับของกราฟเหล่านี้จะลู่เข้าสู่กราฟอนแบบ "สองส่วนสมบูรณ์" ที่กำหนดโดยเมื่อใดก็ตามที่และและกำหนดค่าอื่น ๆ เป็นอย่างอื่น ${\displaystyle n}$${\displaystyle W}$${\displaystyle W(x,y)=1}$${\displaystyle \min(x,y)\leq 1/2}$${\displaystyle \max(x,y)>1/2}$${\displaystyle W(x,y)=0}$

ถ้าเราเรียงลำดับจุดยอดของโดยสลับกันระหว่างส่วนต่างๆ เมทริกซ์ประชิดจะมีโครงสร้างเหมือนกระดานหมากรุกที่มีแต่ศูนย์และหนึ่ง ตัวอย่างเช่น ภายใต้การเรียงลำดับนี้ เมทริกซ์ประชิดของจะมีค่าดังนี้ ${\displaystyle K_{n,n}}$${\displaystyle K_{2,2}}$

$${\displaystyle {\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.}$$

เมื่อมีขนาดใหญ่ขึ้น เมทริกซ์ประชิดจะกลายเป็นกระดานหมากรุกที่ละเอียดขึ้นเรื่อยๆ ถึงแม้จะมีพฤติกรรมเช่นนี้ เราก็ยังต้องการให้ลิมิตของมีค่าเฉพาะและได้ผลลัพธ์เป็นกราฟอนจากตัวอย่างที่ 3 ซึ่งหมายความว่าเมื่อเรากำหนดนิยามการลู่เข้าอย่างเป็นทางการสำหรับลำดับของกราฟ นิยามของลิมิตควรจะไม่ขึ้นอยู่กับการเปลี่ยนชื่อจุดยอด ${\displaystyle n}$${\displaystyle (K_{n,n})}$

เลือกกราฟแบบสุ่มจำนวนหนึ่งโดยการสุ่มเลือกสำหรับกราฟอนที่กำหนดไว้จากนั้นเช่นเดียวกับในตัวอย่างแรกจากส่วนนี้ ปรากฏว่าลู่เข้าสู่เกือบแน่นอน ${\displaystyle (G_{n})}$${\displaystyle W}$${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$${\displaystyle W}$${\displaystyle (G_{n})}$${\displaystyle W}$

เมื่อกำหนดกราฟที่มีกราฟอนที่เกี่ยวข้องเราสามารถกู้คืนคุณสมบัติและพารามิเตอร์ทางทฤษฎีกราฟของ ได้โดยการอินทิเกรตการแปลงของตัวอย่างเช่น ความหนาแน่นของขอบ (เช่น ดีกรีเฉลี่ยหารด้วยจำนวนจุดยอด) ของกำหนดโดยอินทิกรัล เนื่องจากเป็นค่าของ และแต่ละขอบ ใน สอดคล้องกับบริเวณ ที่ มี พื้นที่ซึ่งเท่ากับ${\displaystyle G}$${\displaystyle W=W_{G}}$${\displaystyle G}$${\displaystyle W}$${\displaystyle G}$$${\displaystyle \int _{0}^{1}\int _{0}^{1}W(x,y)\;\mathrm {d} x\,\mathrm {d} y.}$$${\displaystyle W}$${\displaystyle \{0,1\}}$${\displaystyle (i,j)}$${\displaystyle G}$${\displaystyle I_{i}\times I_{j}}$${\displaystyle 1/n^{2}}$${\displaystyle W}$${\displaystyle 1}$

การให้เหตุผลในทำนองเดียวกันแสดงให้เห็นว่าความหนาแน่นของสามเหลี่ยมในนั้นเท่ากับ ${\displaystyle G}$$${\displaystyle {\frac {1}{6}}\int _{0}^{1}\int _{0}^{1}\int _{0}^{1}W(x,y)W(y,z)W(z,x)\;\mathrm {d} x\,\mathrm {d} y\,\mathrm {d} z.}$$

มีหลายวิธีในการวัดระยะห่างระหว่างกราฟสองกราฟ หากเราสนใจเมตริกที่ "รักษา" คุณสมบัติสุดขั้วของกราฟ เราควรจำกัดความสนใจของเราไว้ที่เมตริกที่ระบุว่ากราฟแบบสุ่มมีความคล้ายคลึงกัน ตัวอย่างเช่น หากเราสุ่มเลือกกราฟสองกราฟอย่างอิสระจากแบบจำลอง Erdős–Rényi สำหรับค่าคงที่บางค่าระยะห่างระหว่างกราฟทั้งสองนี้ภายใต้เมตริกที่ "สมเหตุสมผล" ควรใกล้เคียงกับศูนย์ด้วยความน่าจะเป็นสูงสำหรับค่า n ที่มาก ${\displaystyle G(n,p)}$${\displaystyle p}$${\displaystyle n}$

โดยทั่วไปแล้ว หากเรามีกราฟสองกราฟบนเซตจุดยอดเดียวกัน เราอาจกำหนดระยะห่างระหว่างกราฟทั้งสองเป็นจำนวนขอบที่ต้องเพิ่มหรือลบออกเพื่อให้ได้กราฟจากกราฟหนึ่งไปยังอีกกราฟหนึ่ง นั่นคือระยะห่างแบบแก้ไข (edit distance ) อย่างไรก็ตาม ระยะห่างแบบแก้ไขไม่ได้ระบุว่ากราฟแบบสุ่มมีความคล้ายคลึงกัน ในความเป็นจริง กราฟสองกราฟที่สุ่มเลือกอย่างอิสระจากเซตจุดยอดเดียวกันจะมีระยะห่างแบบแก้ไขที่คาดหวัง (แบบนอร์มาไลซ์) เท่ากับ 0.05 ${\displaystyle G(n,{\tfrac {1}{2}})}$${\displaystyle {\tfrac {1}{2}}}$

มีตัวชี้วัดตามธรรมชาติสองตัวที่ทำงานได้ดีกับกราฟสุ่มที่มีความหนาแน่นสูงในแบบที่เราต้องการ ตัวแรกคือตัวชี้วัดการสุ่มตัวอย่าง ซึ่งกล่าวว่ากราฟสองกราฟจะใกล้เคียงกันหากการกระจายของกราฟย่อยของกราฟทั้งสองนั้นใกล้เคียงกัน ตัวที่สองคือ ตัวชี้ วัดความคลาดเคลื่อน ของขอบ ซึ่งกล่าวว่ากราฟสองกราฟจะใกล้เคียงกันเมื่อความหนาแน่นของขอบของกราฟทั้งสองนั้นใกล้เคียงกันในทุกเซตย่อยของจุดยอดที่สอดคล้องกัน

อย่างน่าอัศจรรย์ ลำดับของกราฟจะลู่เข้าตามเมตริกหนึ่งก็ต่อเมื่อมันลู่เข้าตามเมตริกอื่นเท่านั้น ยิ่งไปกว่านั้น วัตถุลิมิตภายใต้เมตริกทั้งสองกลายเป็นกราฟอน ความเท่าเทียมกันของแนวคิดการลู่เข้าทั้งสองนี้สะท้อนให้เห็นว่าแนวคิดต่างๆ ของ กราฟ กึ่งสุ่มนั้นเทียบเท่ากัน อย่างไร ^{[ 7 ]}

วิธีหนึ่งในการวัดระยะห่างระหว่างกราฟสองกราฟคือการเปรียบเทียบจำนวนซับกราฟสัมพัทธ์ของกราฟทั้งสอง กล่าวคือ สำหรับแต่ละกราฟเราสามารถเปรียบเทียบจำนวนสำเนาของในและใน ได้หากตัวเลขเหล่านี้ใกล้เคียงกันสำหรับทุกกราฟแล้วโดยสัญชาตญาณแล้วและจะเป็นกราฟที่ดูคล้ายกัน อย่างไรก็ตาม แทนที่จะจัดการกับซับกราฟโดยตรง ปรากฏว่าการทำงานกับกราฟโฮโมมอร์ฟิซึมนั้นง่ายกว่า ซึ่งเหมาะสมเมื่อจัดการกับกราฟขนาดใหญ่และหนาแน่น เนื่องจากในสถานการณ์นี้ จำนวนซับกราฟและจำนวนกราฟโฮโมมอร์ฟิซึมจากกราฟคงที่นั้นจะเท่ากันในเชิงอะซิมโทติก ${\displaystyle G}$${\displaystyle H}$${\displaystyle F}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle H}$${\displaystyle F}$${\displaystyle G}$${\displaystyle H}$

กำหนดให้กราฟสองกราฟคือ และความ หนาแน่นของโฮโมมอร์ฟิซึมของในถูกกำหนดให้เป็นจำนวนของโฮโมมอร์ฟิซึมกราฟจากไปยังกล่าวอีกนัยหนึ่งคือคือความน่าจะเป็นที่แผนที่ที่เลือกแบบสุ่มจากจุดยอดของไปยังจุดยอดของจะส่งจุดยอดที่อยู่ติดกันในไปยังจุดยอดที่อยู่ติดกันใน ${\displaystyle F}$${\displaystyle G}$${\displaystyle t(F,G)}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle t(F,G)}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$

กราฟอนนำเสนอวิธีที่ง่ายในการคำนวณความหนาแน่นของโฮโมมอร์ฟิซึม ที่จริงแล้ว เมื่อกำหนดกราฟที่มีกราฟอนที่เกี่ยวข้องและอีกกราฟอนหนึ่ง เราจะได้ว่า ${\displaystyle G}$${\displaystyle W_{G}}$${\displaystyle F}$

$${\displaystyle t(F,G)=\int \prod _{(i,j)\in E(F)}W_{G}(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

โดยที่ปริพันธ์เป็นปริพันธ์หลายมิติ ซึ่งคำนวณบนไฮเปอร์คิวบ์หน่วยสิ่งนี้เป็นผลมาจากนิยามของกราฟอนที่เกี่ยวข้อง โดยพิจารณาเมื่อตัวถูกอินทิเกรตข้างต้นเท่ากับ จากนั้นเราสามารถขยายนิยามของความหนาแน่นของโฮโมมอร์ฟิซึมไปยังกราฟอนใดๆ ได้โดยใช้ปริพันธ์เดียวกันและกำหนด ${\displaystyle [0,1]^{V(F)}}$${\displaystyle 1}$${\displaystyle W}$

$${\displaystyle t(F,W)=\int \prod _{(i,j)\in E(F)}W(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

สำหรับกราฟใดๆ ${\displaystyle F}$

จากเงื่อนไขนี้ เรากล่าวว่าลำดับของกราฟลู่เข้าทางซ้ายถ้าสำหรับทุกกราฟที่กำหนดไว้ลำดับของความหนาแน่นของโฮโมมอร์ฟิซึมลู่เข้า แม้ว่าจะไม่ชัดเจนจากนิยามเพียงอย่างเดียว แต่ถ้า ลู่เข้าในความหมายนี้ ก็จะมีกราฟออนอยู่เสมอซึ่งสำหรับทุกกราฟเราจะมี พร้อมกัน ${\displaystyle (G_{n})}$${\displaystyle F}$${\displaystyle \left(t(F,G_{n})\right)}$${\displaystyle (G_{n})}$${\displaystyle W}$${\displaystyle F}$$${\displaystyle \lim _{n\to \infty }t(F,G_{n})=t(F,W)}$$

พิจารณากราฟสองกราฟที่มีเซตจุดยอดเดียวกัน เนื่องจากกราฟทั้งสองมีจุดยอดร่วมกัน วิธีหนึ่งในการวัดระยะห่างระหว่างกราฟทั้งสองคือการจำกัดขอบเขตไปยังเซตย่อยของเซตจุดยอด และสำหรับแต่ละคู่ของเซตย่อยดังกล่าว ให้เปรียบเทียบจำนวนขอบจากจุดยอดหนึ่งไป ยังอีกจุดยอดหนึ่งในกราฟหนึ่ง กับจำนวนขอบระหว่าง จุด ยอดสอง จุดหนึ่งในกราฟหนึ่ง หากจำนวนเหล่านี้ใกล้เคียงกันสำหรับทุกคู่ของเซตย่อย (เมื่อเทียบกับจำนวนจุดยอดทั้งหมด) นั่นแสดงว่ากราฟทั้งสองคล้ายกัน ${\displaystyle G}$${\displaystyle H}$${\displaystyle X,Y}$${\displaystyle e_{G}(X,Y)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle G}$${\displaystyle e_{H}(X,Y)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$

เพื่อเป็นการกำหนดรูปแบบเบื้องต้นของแนวคิดเรื่องระยะทางนี้ สำหรับกราฟสองกราฟใดๆและบนเซตจุดยอดเดียวกันที่มีขนาดให้กำหนดระยะทางตัดที่มีป้ายกำกับระหว่างและเป็น ${\displaystyle G}$${\displaystyle H}$${\displaystyle V}$${\displaystyle |V|=n}$${\displaystyle G}$${\displaystyle H}$

$${\displaystyle d_{\square }(G,H)={\frac {1}{n^{2}}}\max _{X,Y\subseteq V}\left|e_{G}(X,Y)-e_{H}(X,Y)\right|.}$$

กล่าวอีกนัยหนึ่ง ระยะตัดที่ระบุไว้จะเข้ารหัสความคลาดเคลื่อนสูงสุดของความหนาแน่นของขอบระหว่างและเราสามารถขยายแนวคิดนี้ไปยังกราฟอนได้โดยการแสดงความหนาแน่นของขอบในรูปของกราฟอนที่เกี่ยวข้องซึ่งให้ค่าเท่ากัน ${\displaystyle G}$${\displaystyle H}$${\displaystyle {\tfrac {1}{n^{2}}}e_{G}(X,Y)}$${\displaystyle W_{G}}$

$${\displaystyle d_{\square }(G,H)=\max _{X,Y\subseteq V}\left|\int _{I_{X}}\int _{I_{Y}}W_{G}(x,y)-W_{H}(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$

โดยที่เป็นการรวมกันของช่วงเวลาที่สอดคล้องกับจุดยอดในและโปรดทราบว่าคำจำกัดความนี้ยังคงสามารถใช้ได้แม้ว่ากราฟที่นำมาเปรียบเทียบกันจะไม่มีเซตจุดยอดร่วมกันก็ตาม นี่เป็นแรงบันดาลใจให้เกิดคำจำกัดความที่ครอบคลุมมากขึ้นดังต่อไปนี้ ${\displaystyle I_{X},I_{Y}\subseteq [0,1]}$${\displaystyle X}$${\displaystyle Y}$

นิยาม 1.สำหรับฟังก์ชันสมมาตรที่วัดได้ใดๆให้กำหนดนอร์มตัดของ ฟังก์ชันนั้น ว่าเป็นปริมาณ ${\displaystyle f:[0,1]^{2}\to \mathbb {R} }$${\displaystyle f}$

$${\displaystyle \lVert f\rVert _{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S}\int _{T}f(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$ ครอบคลุมทุกเซตย่อยที่วัดได้ของช่วงหน่วย^{[ 6 ]}${\displaystyle S,T}$

สิ่งนี้สะท้อนถึงแนวคิดก่อนหน้านี้ของเราเกี่ยวกับระยะตัดที่มีป้ายกำกับ เนื่องจากเรามีความเท่าเทียมกัน ${\displaystyle \lVert W_{G}-W_{H}\rVert _{\square }=d_{\square }(G,H)}$

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

นิยามที่ 2.สำหรับกราฟอนคู่ใดๆและให้กำหนดระยะตัด ของกราฟอนทั้งสอง เป็น ${\displaystyle U}$${\displaystyle W}$

$${\displaystyle \delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }}$$ โดยที่การประกอบของกับแผนที่และค่าต่ำสุดจะถูกหาจาก ฟังก์ชันหนึ่งต่อหนึ่ง ที่รักษาการวัด ทั้งหมด จากช่วงหน่วยไปยังตัวมันเอง^{[ 8 ]}${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$${\displaystyle W}$${\displaystyle \varphi }$

ระยะตัดระหว่างกราฟสองกราฟถูกกำหนดให้เป็นระยะตัดระหว่างกราฟอนที่เกี่ยวข้องของกราฟทั้งสองนั้น

เรากล่าวว่าลำดับของกราฟลู่เข้าภายใต้ระยะตัดถ้าลำดับนั้นเป็นลำดับโคชีภายใต้ระยะตัด แม้จะไม่ใช่ผลลัพธ์โดยตรงจากนิยาม แต่ถ้าหากลำดับของกราฟดังกล่าวเป็นลำดับโคชีแล้ว มันจะลู่เข้าสู่กราฟ อน เสมอ${\displaystyle (G_{n})}$${\displaystyle \delta _{\square }}$${\displaystyle W}$

ปรากฏว่าสำหรับลำดับของกราฟใดๆการลู่เข้าทางซ้ายเทียบเท่ากับการลู่เข้าภายใต้ระยะทางตัด และยิ่งไปกว่านั้น กราฟอนลิมิตก็เหมือนกัน เรายังสามารถพิจารณาการลู่เข้าของกราฟอนเองโดยใช้คำจำกัดความเดียวกัน และความเท่าเทียมกันเดียวกันก็เป็นจริง ในความเป็นจริง แนวคิดทั้งสองของการลู่เข้ามีความสัมพันธ์กันอย่างแน่นแฟ้นยิ่งขึ้นผ่านสิ่งที่เรียกว่าบทพิสูจน์การนับ^{[ 6 ]}${\displaystyle (G_{n})}$${\displaystyle W}$

ทฤษฎีบทนับสำหรับกราฟอนคู่ใดๆและเรามี ${\displaystyle U}$${\displaystyle W}$

$${\displaystyle |t(F,U)-t(F,W)|\leq e(F)\delta _{\square }(U,W)}$$สำหรับ กราฟ ทั้งหมด${\displaystyle F}$

ชื่อ "บทพิสูจน์การนับ" มาจากขอบเขตที่บทพิสูจน์นี้ให้ไว้สำหรับความหนาแน่นของโฮโมมอร์ฟิซึม ซึ่งคล้ายคลึงกับการนับกราฟย่อยของกราฟ บทพิสูจน์นี้เป็นการวางนัยทั่วไปของบทพิสูจน์การนับกราฟที่ปรากฏในสาขาของการแบ่งส่วนความสม่ำเสมอและแสดงให้เห็นทันทีว่าการลู่เข้าภายใต้ระยะทางตัดหมายถึงการลู่เข้าทางซ้าย ${\displaystyle t(F,W)}$

ทฤษฎีบทการนับผกผันสำหรับจำนวนจริงทุกจำนวนจะมีจำนวนจริงและจำนวนเต็มบวก อยู่จำนวนหนึ่ง ซึ่งสำหรับกราฟอนคู่ใดๆและที่มี ${\displaystyle \varepsilon >0}$${\displaystyle \eta >0}$${\displaystyle k}$${\displaystyle U}$${\displaystyle W}$

$${\displaystyle |t(F,U)-t(F,W)|\leq \eta }$$ สำหรับกราฟทั้งหมดที่สอดคล้องกับเงื่อนไขเราจะต้องมีเงื่อนไขดังกล่าว ${\displaystyle F}$${\displaystyle v(F)\leq k}$${\displaystyle \delta _{\square }(U,W)<\varepsilon }$

บทพิสูจน์ย่อยนี้แสดงให้เห็นว่าการลู่เข้าทางซ้ายหมายถึงการลู่เข้าภายใต้ระยะตัด

เราสามารถสร้างเมตริกโดยการนำเซตของกราฟอนทั้งหมดมา แล้วระบุกราฟอนสองตัวเมื่อใดก็ตามที่เงื่อนไขเป็นจริง ปริภูมิของกราฟอนที่ได้จะถูกแทนด้วยและเมื่อรวมกับจะก่อให้เกิดปริภูมิ เมตริก${\displaystyle U\sim W}$${\displaystyle \delta _{\square }(U,W)=0}$${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$${\displaystyle \delta _{\square }}$

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

บทแทรก 1.สำหรับจำนวนจริงทุกจำนวนจะมีจำนวนเต็มเช่นนั้น สำหรับกราฟอนทุกตัวจะมีกราฟที่มีจุดยอดไม่เกินเช่นนั้น ${\displaystyle \varepsilon >0}$${\displaystyle N}$${\displaystyle W}$${\displaystyle G}$${\displaystyle N}$${\displaystyle \delta _{\square }(W,W_{G})<\varepsilon }$

เพื่อให้เข้าใจเหตุผล ลองให้เป็นเซตของกราฟ พิจารณาสำหรับแต่ละกราฟลูกบอลเปิดที่บรรจุกราฟอนทั้งหมดซึ่งเซตของลูกบอลเปิดสำหรับกราฟทั้งหมดครอบคลุมดังนั้นความกะทัดรัดจึงหมายความว่ามีซับคัฟเวอร์จำกัดสำหรับเซตย่อยจำกัดบางเซตตอนนี้เราสามารถเลือกให้เป็นจำนวนจุดยอดที่มากที่สุดในบรรดากราฟใน ${\displaystyle {\mathcal {G}}}$${\displaystyle G\in {\mathcal {G}}}$${\displaystyle B_{\square }(G,\varepsilon )}$${\displaystyle W}$${\displaystyle \delta _{\square }(W,W_{G})<\varepsilon }$${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$${\displaystyle \{B_{\square }(G,\varepsilon )\mid G\in {\mathcal {G}}_{0}\}}$${\displaystyle {\mathcal {G}}_{0}\subset {\mathcal {G}}}$${\displaystyle N}$${\displaystyle {\mathcal {G}}_{0}}$

ความกะทัดรัดของพื้นที่กราฟอนสามารถคิดได้ว่าเป็นการกำหนดสูตรเชิงวิเคราะห์ของทฤษฎีบทความสม่ำเสมอของ Szemerédiในความเป็นจริง ผลลัพธ์ที่แข็งแกร่งกว่าทฤษฎีบทดั้งเดิม^{[ 9 ]} ทฤษฎีบทความสม่ำเสมอของ Szemerédi สามารถแปลเป็นภาษาของกราฟอนได้ดังนี้ กำหนดให้ฟังก์ชันขั้นบันไดเป็นกราฟอนที่มีค่าคงที่แบบเป็นช่วง กล่าวคือ สำหรับการแบ่งส่วนบางส่วนของ จะเป็น ค่าคงที่บนสำหรับทุกข้อความที่ระบุว่ากราฟมีการแบ่งส่วนความสม่ำเสมอเทียบเท่ากับการกล่าวว่ากราฟอนที่เกี่ยวข้องนั้นใกล้เคียงกับฟังก์ชันขั้นบันได ${\displaystyle ({\widetilde {\mathcal {W}}}_{0},\delta _{\square })}$${\displaystyle W}$${\displaystyle {\mathcal {P}}}$${\displaystyle [0,1]}$${\displaystyle W}$${\displaystyle S\times T}$${\displaystyle S,T\in {\mathcal {P}}}$${\displaystyle G}$${\displaystyle W_{G}}$

การพิสูจน์ความกะทัดรัดนั้นต้องการเพียงบทพิสูจน์ความสม่ำเสมอแบบอ่อน เท่านั้น :

ทฤษฎีบทความสม่ำเสมอแบบอ่อนสำหรับกราฟอนสำหรับทุกกราฟอนและจะมีฟังก์ชันขั้นบันไดที่มีจำนวนขั้นไม่เกินเช่นนั้น ${\displaystyle W}$${\displaystyle \varepsilon >0}$${\displaystyle W'}$${\displaystyle \lceil 4^{1/\varepsilon ^{2}}\rceil }$${\displaystyle \lVert W-W'\rVert _{\square }\leq \varepsilon }$

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

บทพิสูจน์ความสม่ำเสมอที่เข้มงวดสำหรับกราฟอนสำหรับทุกลำดับของจำนวนจริงบวก จะมีจำนวนเต็มบวกตัวหนึ่งที่ทำให้สำหรับทุกกราฟอนจะมีกราฟอนและฟังก์ชันขั้นบันไดที่มีขั้นบันได เช่นนั้นและ${\displaystyle \mathbf {\varepsilon } =(\varepsilon _{0},\varepsilon _{1},\dots )}$${\displaystyle S}$${\displaystyle W}$${\displaystyle W'}$${\displaystyle U}$${\displaystyle k<S}$${\displaystyle \lVert W-W'\rVert _{1}\leq \varepsilon _{0}}$${\displaystyle \lVert W'-U\rVert _{\square }\leq \varepsilon _{k}.}$

การพิสูจน์บทตั้งความสม่ำเสมอที่เข้มงวดนั้นมีแนวคิดคล้ายกับบทสรุปที่ 1 ข้างต้น ปรากฏว่ากราฟอนทุกตัวสามารถประมาณได้ด้วยฟังก์ชันขั้นบันไดในนอร์มซึ่งแสดงให้เห็นว่าเซตของทรงกลมครอบคลุมเซตเหล่านี้ เซตเหล่านี้ไม่ใช่เซตเปิดในเมตริก แต่สามารถขยายเล็กน้อยเพื่อให้เป็นเซตเปิดได้ ตอนนี้เราสามารถเลือกซับคัฟเวอร์แบบจำกัด และสามารถแสดงได้ว่าเงื่อนไขที่ต้องการนั้นเป็นไปตามนั้น ${\displaystyle W}$${\displaystyle U}$${\displaystyle L_{1}}$${\displaystyle B_{1}(U,\varepsilon _{0})}$${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$${\displaystyle \delta _{\square }}$

ลักษณะเชิงวิเคราะห์ของกราฟอนช่วยให้มีความยืดหยุ่นมากขึ้นในการแก้ปัญหาความไม่เท่าเทียมกันที่เกี่ยวข้องกับโฮโมมอร์ฟิซึม

ตัวอย่างเช่น ข้อสันนิษฐานของ Sidorenko เป็นปัญหาเปิดที่สำคัญในทฤษฎีกราฟสุดขั้วซึ่งยืนยันว่าสำหรับกราฟใดๆบนจุดยอดที่มีดีกรีเฉลี่ย(สำหรับบางค่า) และกราฟสองส่วนบนจุดยอดและขอบ จำนวนโฮโมมอร์ฟิซึมจากไป ยัง มี ค่าอย่างน้อย^{[ 10 ]} เนื่องจากปริมาณนี้คือจำนวนที่คาดหวังของกราฟย่อยที่มีป้ายกำกับของในกราฟสุ่มข้อสันนิษฐานจึงสามารถตีความได้ว่าเป็นข้ออ้างที่ว่าสำหรับกราฟสองส่วนใดๆกราฟสุ่มจะบรรลุ (โดยเฉลี่ย) จำนวนสำเนาขั้นต่ำของเหนือกราฟทั้งหมดที่มีความหนาแน่นของขอบคงที่ ${\displaystyle G}$${\displaystyle n}$${\displaystyle pn}$${\displaystyle p\in [0,1]}$${\displaystyle H}$${\displaystyle v}$${\displaystyle e}$${\displaystyle H}$${\displaystyle G}$${\displaystyle p^{e}n^{v}}$${\displaystyle H}$${\displaystyle G(n,p)}$${\displaystyle H}$${\displaystyle H}$

แนวทางมากมายในการพิจารณาสมมติฐานของ Sidorenko กำหนดปัญหาเป็นอสมการเชิงอินทิกรัลบนกราฟอน ซึ่งทำให้สามารถโจมตีปัญหาโดยใช้แนวทางการวิเคราะห์อื่นๆ ได้^{[ 11 ]}

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