มุมมองระยะใกล้เผยให้เห็นจุด 'หลอมละลาย' ของกราฟที่ไม่มีที่สิ้นสุด | นิตยสารควอนต้า

ในปี 2008 นักคณิตศาสตร์ Oded Schramm เสียชีวิตจากอุบัติเหตุเดินป่าในเทือกเขา Cascade ห่างจากซีแอตเทิลไปทางตะวันออกประมาณ 50 ไมล์ แม้ว่าเขาจะอายุเพียง 46 ปี แต่เขาได้สร้างสาขาวิชาคณิตศาสตร์ใหม่ทั้งหมด

“เขาเป็นนักคณิตศาสตร์ที่ยอดเยี่ยม” กล่าว อิไต เบนจามินีนักคณิตศาสตร์จากสถาบันวิทยาศาสตร์ Weizmann และเพื่อนและผู้ร่วมงานของ Schramm “สร้างสรรค์อย่างยิ่ง หรูหราอย่างยิ่ง ดั้งเดิมอย่างยิ่ง”

คำถามที่เขาถามยังคงผลักดันขอบเขตของทฤษฎีความน่าจะเป็นและฟิสิกส์เชิงสถิติ คำถามเหล่านี้หลายข้อเกี่ยวข้องกับโครงสร้างทางคณิตศาสตร์ที่มีการเปลี่ยนเฟส ซึ่งเป็นการเปลี่ยนแปลงระดับมหภาคอย่างกะทันหัน เช่น น้ำแข็งละลายเป็นน้ำ เช่นเดียวกับที่วัสดุต่างกันมีจุดหลอมเหลวต่างกัน การเปลี่ยนเฟสของโครงสร้างทางคณิตศาสตร์ก็แตกต่างกันไปเช่นกัน

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

ใน พิมพ์ล่วงหน้าโพสต์ในเดือนตุลาคม, ทอม ฮัทช์ครอฟต์ ของสถาบันเทคโนโลยีแคลิฟอร์เนียและนักศึกษาปริญญาเอกของเขา ฟิลิป อีโซ พิสูจน์การคาดเดาเกี่ยวกับท้องถิ่นของ Schramm การพิสูจน์ของพวกเขาอาศัยแนวคิดหลักๆ จากทฤษฎีความน่าจะเป็นและด้านอื่นๆ ของคณิตศาสตร์ ซึ่งพวกเขานำมารวมกันอย่างชาญฉลาด

“มันเป็นรายงานที่น่าทึ่ง มันเป็นการสะสมของการทำงานที่ยาวนาน” เบนจามินีกล่าว

คลัสเตอร์ที่ไม่มีที่สิ้นสุด

คำว่า "การซึมผ่าน" เดิมหมายถึงการเคลื่อนที่ของของไหลผ่านตัวกลางที่มีรูพรุน เช่น น้ำที่ไหลผ่านกากกาแฟ หรือน้ำมันที่ซึมผ่านรอยแตกในหิน

ในปี 1957 นักคณิตศาสตร์ ไซมอน ราล์ฟ บรอดเบนต์ และจอห์น ไมเคิล แฮมเมอร์สลีย์ ได้พัฒนาแบบจำลองทางคณิตศาสตร์ของกระบวนการทางกายภาพนี้ ในช่วงหลายทศวรรษนับตั้งแต่นั้นเป็นต้นมา โมเดลนี้ได้กลายเป็นเป้าหมายของการศึกษาในตัวมันเอง นักคณิตศาสตร์ศึกษาการซึมผ่านเนื่องจากมีจุดสมดุลที่สำคัญ: การตั้งค่านั้นเรียบง่าย แต่แสดงคุณลักษณะที่ซับซ้อนและเป็นปริศนา

“มันเป็นแบบจำลองที่เป็นที่ยอมรับสำหรับนักคณิตศาสตร์” ฮัทช์ครอฟต์กล่าว “คุณสามารถคิดถึงสิ่งต่าง ๆ ได้ด้วยสายตา นั่นทำให้รู้สึกดีที่ได้ร่วมงานด้วย”

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

ไม่นานก่อนที่เขาจะเสียชีวิต Schramm คาดเดาว่าทฤษฎีบทของกริมเมตต์และมาร์สตรันด์สามารถสรุปได้ทั่วไป เขาคิดว่าเกณฑ์การซึมผ่านถูกกำหนดโดยมุมมองระยะใกล้หรือ "กล้องจุลทรรศน์" สำหรับกราฟขนาดใหญ่ที่เรียกว่ากราฟสกรรมกริยา

ในปี พ.ศ. 2009 เบนจามินี อาซาฟ นาชเมียส และ ยูวัล เปเรส พิสูจน์แล้วว่า ดังที่ทราบกันดีอยู่แล้วว่าการคาดเดาเกี่ยวกับท้องถิ่นของ Schramm สำหรับกราฟสกรรมกริยาประเภทหนึ่งที่มีลักษณะคล้ายต้นไม้ อย่างไรก็ตาม Schramm ได้ตั้งสมมุติฐานว่าจะคงไว้สำหรับกราฟสกรรมกริยาทั้งหมด (ยกเว้นกราฟหนึ่งมิติ)

ในกราฟสกรรมกริยา จุดยอดทั้งหมดจะมีลักษณะคล้ายกัน ตารางสองมิติเป็นตัวอย่างหนึ่ง หากคุณเลือกจุดยอดใดๆ สองจุด คุณจะพบความสมมาตรที่ย้ายจุดยอดหนึ่งไปยังอีกจุดหนึ่งได้ตลอดเวลา

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

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

กราฟสกรรมกริยาที่หลากหลายมีส่วนทำให้ความยากลำบากในการพิสูจน์การคาดเดาเกี่ยวกับท้องถิ่นของ Schramm ในช่วง 15 ปีระหว่างการคาดเดาของ Schramm และการพิสูจน์ของ Easo และ Hutchcroft นักคณิตศาสตร์กลุ่มต่างๆ ได้พิสูจน์การคาดเดาสำหรับกราฟบางประเภท แต่แนวคิดของพวกเขาไม่เคยขยายไปสู่กรณีทั่วไป

“พื้นที่ของรูปทรงเรขาคณิตที่เป็นไปได้ทั้งหมดนั้นกว้างใหญ่มากและมีสิ่งแปลก ๆ ซุ่มซ่อนอยู่เสมอ” ฮัทช์ครอฟต์กล่าว

การขยายเลนส์

ในตอนแรก Easo และ Hutchcroft ไม่ได้มองหาวิธีแก้ปัญหาสำหรับการคาดเดาเกี่ยวกับท้องถิ่นของ Schramm ซึ่งนำไปใช้กับกราฟที่ไม่มีที่สิ้นสุด พวกเขากำลังศึกษาการซึมผ่านบนกราฟจำกัดแทน แต่พวกเขามีความคิดที่จู่ๆ ก็เปลี่ยนความสนใจไปที่การคาดเดา

“เราได้เครื่องมือใหม่นี้ขึ้นมา และเราคิดว่า โอ้ ดูเหมือนว่าจะเป็นสิ่งที่มีประโยชน์ในการโจมตีในพื้นที่” Easo กล่าว

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

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

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

พวกเขาสามารถแสดงให้เห็นว่าคลัสเตอร์ขนาดใหญ่เติบโตเร็วกว่าคลัสเตอร์ขนาดเล็ก ดังนั้น ตามที่ Easo กล่าว “คลัสเตอร์ของคุณเติบโตเร็วขึ้นและเร็วขึ้นเมื่อมันใหญ่ขึ้นเรื่อยๆ เช่นเดียวกับเมื่อคุณกลิ้งก้อนหิมะ”

สำหรับตารางสี่เหลี่ยม จำนวนจุดยอดจะเพิ่มขึ้นค่อนข้างช้า มันคือความกว้างของเลนส์โดยประมาณกำลังสอง หลังจาก 10 ขั้นตอน คุณจะพบจุดยอดประมาณ 100 จุด แต่ต้นไม้ธรรมดา 3 ต้นจะเติบโตเร็วขึ้นแบบทวีคูณ โดยเพิ่มขึ้นประมาณ 2 ต้นตามกำลังความกว้างของเลนส์ของคุณ หลังจาก 10 ขั้นตอน คุณจะเห็นจุดยอดประมาณ 1,024 จุด ภาพประกอบด้านล่างแสดงให้เห็นว่าต้นไม้ธรรมดา 3 ต้นมีขนาดใหญ่ขึ้นมากเพียงใดหลังจากผ่านไปเพียง XNUMX ขั้นตอน แม้ว่าตารางสี่เหลี่ยมจัตุรัสจะมีจุดยอดมากกว่าในตอนแรกก็ตาม โดยทั่วไป กราฟอาจมีอัตราการเติบโตที่แตกต่างกันในระดับที่แตกต่างกัน โดยอาจเริ่มต้นอย่างรวดเร็วแล้วจึงช้าลง

ย้อนกลับไปในปี 2018 ฮัทช์ครอฟต์ ก็ใช้ความคิดที่คล้ายกัน เพื่อพิสูจน์การคาดเดาท้องถิ่นสำหรับกราฟที่เติบโตอย่างรวดเร็วเช่นต้นไม้ 3 ต้น แต่มันใช้ไม่ได้กับกราฟที่เติบโตช้า เช่น ตารางสี่เหลี่ยม หรือกราฟที่เติบโตที่ความเร็วปานกลาง ซึ่งไม่ตรงตามเกณฑ์ทางคณิตศาสตร์สำหรับการเติบโตอย่างรวดเร็วหรือการเติบโตช้า

“นี่คือสิ่งที่น่าหงุดหงิดจริงๆ เป็นเวลาสามปี” ฮัทช์ครอฟต์กล่าว

โครงสร้างเทียบกับการขยายตัว

สำหรับกราฟที่ผสมอัตราการเติบโตในระดับต่างๆ คุณต้องใช้เทคนิคที่หลากหลาย

ข้อเท็จจริงที่เป็นประโยชน์ประการหนึ่งก็คือ ตามที่ Easo อธิบายไว้ “หากกราฟดูเติบโตช้าในระดับหนึ่ง กราฟนั้นก็จะติดอยู่” มันจะเติบโตต่อไปอย่างช้าๆ ในขนาดที่ใหญ่ขึ้น เนื่องจากกราฟการเติบโตช้ามีโครงสร้างเพิ่มเติมที่กำหนดโดยสาขาวิชาคณิตศาสตร์ที่เรียกว่าทฤษฎีกลุ่ม เป็นที่ทราบกันดีว่าหากคุณซูมออกให้ไกลเพียงพอ กราฟการเติบโตช้าจะแสดงรูปทรงเรขาคณิตที่เชื่องทางคณิตศาสตร์ได้

ในปี 2021 Sébastien Martineau จากมหาวิทยาลัยซอร์บอนน์ในปารีส ทำงานร่วมกับ Daniel Contreras และ วินเซนต์ ทัสชั่น ของ ETH Zurich สามารถใช้ทรัพย์สินนี้ได้ พิสูจน์การคาดเดาเกี่ยวกับท้องถิ่นของ Schramm สำหรับกราฟที่เติบโตช้าในที่สุด

เมื่อมาถึงจุดนี้ นักคณิตศาสตร์ทั้งสองกลุ่มประสบความสำเร็จในการคาดเดาจากทิศทางที่ต่างกัน: เติบโตอย่างรวดเร็วและเติบโตช้า แต่สิ่งนี้ทำให้เกิดช่องว่างขนาดใหญ่ ประการแรก มีหมวดหมู่การเติบโตระดับกลางที่ไม่ครอบคลุมโดยเทคนิคของ Easo และ Hutchcroft หรือโดยการพิสูจน์ของ Contreras, Martineau และ Tassion ปัญหาอีกประการหนึ่งคือข้อโต้แย้งยังคงใช้ไม่ได้กับกราฟที่อัตราการเติบโตเปลี่ยนแปลง มีเพียงกราฟที่ยังอยู่เร็วหรืออยู่ช้าเท่านั้น สำหรับอาร์กิวเมนต์ Contreras, Martineau และ Tassion ที่จะนำไปใช้กับกราฟตามอำเภอใจนั้น ยังไม่เพียงพอที่ในที่สุดเรขาคณิตจะดูเชื่องเมื่อคุณซูมออก Easo อธิบายว่า: "เราต้องการให้มันดูเชื่องตอนนี้ ใกล้กับสเกลปัจจุบัน"

กลางไม่มีที่ไหนเลย

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

Easo และ Hutchcroft ใช้เวลาส่วนใหญ่ในปีที่ผ่านมาเพื่อขยายผลลัพธ์เพื่อนำไปใช้กับกราฟที่ไม่ครอบคลุมอยู่ในวิธีการใดๆ ก่อนหน้านี้

ขั้นแรก พวกเขาปรับเปลี่ยนเทคนิคปี 2018 ที่ Hutchcroft นำไปใช้กับกราฟที่เติบโตอย่างรวดเร็วเพื่อทำงานกับกราฟที่เปลี่ยนระดับการเติบโตในระดับต่างๆ จากนั้นพวกเขาก็จัดการกับกรณีที่เติบโตช้า กระดาษ 27 หน้า พวกเขาเล่าในเดือนสิงหาคมว่าขยายงานเรื่อง Contreras, Martineau และ Tassion ในที่สุด ในการพิมพ์ล่วงหน้าเดือนตุลาคม พวกเขาคิดค้นข้อโต้แย้งอีกข้อหนึ่งโดยใช้ทฤษฎีการเดินแบบสุ่ม ซึ่งเป็นเส้นที่กระดิกแบบสุ่มไปในอวกาศ เพื่อจัดการกับกรณีการเติบโตระดับกลาง เมื่อการผ่าตัด Trichotomy เสร็จสมบูรณ์ พวกเขาก็พิสูจน์การคาดเดาเกี่ยวกับท้องถิ่นของ Schramm ได้

“เราต้องโยนทุกสิ่งที่เรารู้ไปที่ปัญหา” ฮัทช์ครอฟต์กล่าว

โซลูชันนี้ช่วยให้นักคณิตศาสตร์มีความเข้าใจที่ดีขึ้นเกี่ยวกับสิ่งที่เกิดขึ้นเหนือเกณฑ์การซึมผ่าน โดยที่โอกาสของกระจุกดาวไม่สิ้นสุดคือ 100% และต่ำกว่านั้น โดยที่โอกาสคือ 0% แต่นักคณิตศาสตร์ยังคงนิ่งงันกับสิ่งที่เกิดขึ้นตรงเกณฑ์สำหรับกราฟส่วนใหญ่ รวมถึงตารางสามมิติด้วย “นั่นอาจเป็นคำถามเปิดที่โด่งดังและเป็นพื้นฐานที่สุดในทฤษฎีการซึมผ่าน” กล่าว รัสเซลล์ ลีออนส์ ของมหาวิทยาลัยอินดีแอนา

ตารางสองมิติเป็นหนึ่งในไม่กี่กรณีที่นักคณิตศาสตร์ได้พิสูจน์ว่าเกิดอะไรขึ้นที่เกณฑ์ นั่นคือกระจุกที่ไม่มีที่สิ้นสุดไม่ก่อตัวขึ้น และหลังจากที่ Grimmett และ Marstrand พิสูจน์เวอร์ชันของการคาดเดาเกี่ยวกับท้องถิ่นสำหรับแผ่นคอนกรีตขนาดใหญ่ Grimmett และผู้ทำงานร่วมกันก็แสดงให้เห็นว่า ถ้าคุณแบ่งตาราง 3 มิติออกเป็นสองส่วนในแนวนอน สร้างพื้นขึ้นมา และปรับแป้นหมุนให้ตรงกับเกณฑ์การซึมผ่าน จะไม่มีกระจุกที่ไม่มีที่สิ้นสุดปรากฏขึ้น ผลลัพธ์บอกเป็นนัยว่าตารางสามมิติเต็มรูปแบบ อาจไม่มีกระจุกดาวที่ไม่มีที่สิ้นสุดที่เกณฑ์การซึมผ่าน เช่นเดียวกับตารางสองมิติ

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

การแก้ไข: December 18, 2023
จำนวนโหนดภายใน n ลิงก์ของโหนดเริ่มต้นบนกราฟปกติ 3 เส้นจะเพิ่มขึ้นเมื่อประมาณ 2ⁿไม่ใช่ 3ⁿ ตามที่บทความนี้ระบุไว้เดิม บทความนี้ได้รับการแก้ไขแล้ว

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