พิจารณาลำดับของ${\displaystyle (G_{n})}$กราฟสุ่ม Erdős–Rényi${\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}}}$มีเมทริกซ์บล็อก "ครึ่งสี่เหลี่ยม" สองมุมที่เต็มไปด้วยเลข 1 โดยที่ค่าในช่องที่เหลือเท่ากับศูนย์ ตัวอย่างเช่น เมทริกซ์ประชิดของ${\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})}$มีลักษณะเหมือนเมทริกซ์บล็อกนอกแนวทแยงมุม โดยมีบล็อกเลข 1 สองบล็อกและบล็อกเลข 0 สองบล็อก ตัวอย่างเช่น เมทริกซ์ประชิดของ${\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}}.}$$

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

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

วิธีหนึ่งในการวัดระยะห่างระหว่างกราฟสองกราฟ${\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|}$$ ครอบคลุมเซตย่อยที่วัดได้ทั้งหมด${\displaystyle S,T}$ของช่วงหน่วย^{[ 6 ]}

สิ่งนี้สะท้อนถึงแนวคิดก่อนหน้านี้ของเราเกี่ยวกับระยะตัดที่มีป้ายกำกับ เนื่องจากเรามีความเท่าเทียมกัน${\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 }}$$ ที่ไหน${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$คือองค์ประกอบของ${\displaystyle W}$ด้วยแผนที่${\displaystyle \varphi }$และค่าต่ำสุดจะถูกหาจาก ฟังก์ชันหนึ่งต่อหนึ่ง ที่รักษาการวัด ทั้งหมด จากช่วงหน่วยไปยังตัวมันเอง^{[ 8 ]}

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

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

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

ทฤษฎีบทนับสำหรับกราฟอนคู่ใดๆ${\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 }$.

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