การก้าวกระโดดเล็ก ๆ ที่ยิ่งใหญ่มากในทฤษฎีกราฟ

เมื่อวันที่ 15 มีนาคม ประกาศการสัมมนาที่น่าสนใจได้ส่งเสียงดังก้องไปทั่วสาขา combinatorics ซึ่งเป็นการศึกษาทางคณิตศาสตร์เกี่ยวกับการนับ ผู้ทำงานร่วมกันสามคนวางแผนที่จะพูดคุยประสานงานในวันรุ่งขึ้น จูเลียน สหัสราพุทธิ จะไปปราศรัยกับนักคณิตศาสตร์ในเมืองเคมบริดจ์ ประเทศอังกฤษ ในขณะที่ ไซมอน กริฟฟิธส์ จะแบ่งปันข่าวในริโอเดจาเนโรและ มาร์เซโล กัมโปส ในเซาเปาโล การปราศรัยทั้งสามใช้ชื่อเรื่องเหมือนกันและมีความคลุมเครือ บทคัดย่อ 1996 ประโยคที่อ้างถึง “ความคืบหน้าล่าสุดเกี่ยวกับปัญหาเก่าของแอร์โดส” ในขณะที่ Paul Erdős นักคณิตศาสตร์ชาวฮังกาเรียนซึ่งเสียชีวิตในปี XNUMX ได้โพสต์ หลายร้อยปัญหา ในอาชีพของเขา combinatorists ได้ทำนายประเด็นเฉพาะที่ทั้งสามคนวางแผนจะพูดถึงอย่างรวดเร็ว มีข่าวลือแพร่สะพัดเกี่ยวกับสิ่งที่เรียกว่าเลขแรมซีย์ ซึ่งเป็นหนึ่งในจำนวนที่คำนวณยากที่สุดในคณิตศาสตร์ทั้งหมด

ตัวเลขของแรมซีย์ทำให้เกิดระเบียบวินัยทั้งหมดที่เรียกว่าทฤษฎีแรมซีย์ ซึ่งมองหารูปแบบที่หลีกเลี่ยงไม่ได้ในระบบต่างๆ มากมาย

ตัวอย่างเช่น สมมติว่าคุณพยายามกระจายจำนวนเต็มทั้งหมดในกลุ่มจำนวนหนึ่ง และคุณต้องการหลีกเลี่ยงการวางลำดับของตัวเลขที่เว้นระยะเท่าๆ กันในกลุ่มใดๆ ทฤษฎีแรมซีย์แสดงให้เห็นว่าคุณจะล้มเหลว (เว้นแต่คุณจะมีเงินเหลือเฟือ) ทฤษฎีนี้สามารถนำไปใช้กับทุกสิ่งที่คุณสามารถนับได้ บทเรียนสำคัญของมันคือ "คุณไม่สามารถสร้างระบบที่วุ่นวายได้อย่างสมบูรณ์" Benny Sudakov นักคณิตศาสตร์จาก Swiss Federal Institute of Technology Zurich กล่าว

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

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

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

สายปาร์ตี้

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

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

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

แต่ขนาดของเบอร์แรมซีย์นั้นยากจะคาดเดา ในปี 1935 ห้าปีหลังจากที่แรมซีย์แสดงให้เห็นว่ามีอยู่จริง แอร์โดสและจอร์จ เซเคเรสได้กำหนดขอบเขตบนใหม่ที่เข้มงวดยิ่งขึ้นว่าตัวเลขแรมซีย์มีขนาดใหญ่เพียงใดสำหรับกลุ่มที่มีขนาดที่กำหนด แต่ตั้งแต่นั้นมา นักคณิตศาสตร์แทบจะไม่สามารถปรับปรุงการคำนวณของ Erdős และ Szekeres เลย

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

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

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

ไม่ยากที่จะแสดงว่าหมายเลขแรมซีย์สำหรับกลุ่มขนาด 3 หรือ R(3) คือ 6 (ดูกราฟิก) แต่จนกระทั่งปี 1955 R(4) ถูกตรึงไว้ที่ 18 R(5) ยังไม่ทราบแน่ชัด — อย่างน้อยที่สุดก็ 43 และไม่เกิน 48 แม้ว่าตัวเลขเหล่านี้จะน้อย แต่การกลั่นกรองสีที่เป็นไปได้ทั้งหมดก็หมดลง David Conlon จากสถาบันเทคโนโลยีแห่งแคลิฟอร์เนียกล่าวว่าคำถามนี้ พิจารณาจำนวนสีบนกราฟที่สมบูรณ์ซึ่งมี 43 โหนด “คุณมี 903 ขอบ; แต่ละสีสามารถลงสีได้สองแบบ” เขาอธิบาย “ดังนั้นคุณจะได้รับ 2⁹⁰³ซึ่งมีขนาดใหญ่มากทางดาราศาสตร์”

เมื่อขนาดของกลุ่มเพิ่มขึ้น งานในการตอกย้ำหมายเลขแรมซีย์ก็ยิ่งยากขึ้นเท่านั้น Erdősเหน็บว่าการทำสงครามกับมนุษย์ต่างดาวที่เรียกร้องทางคณิตศาสตร์จะง่ายกว่าการพยายาม คิดออก R(6)ซึ่งอยู่ระหว่าง 102 ถึง 165 ช่วงของความไม่แน่นอนเพิ่มขึ้นอย่างรวดเร็ว: อ้างอิงจาก ประมาณการที่รวบรวมโดย Stanisław Radziszowski, R(10) อาจมีขนาดเล็กได้ถึง 798 และใหญ่ได้ถึง 23,556 แต่เป้าหมายของนักคณิตศาสตร์ไปไกลกว่าตัวเลขแรมซีย์ที่ 10 พวกเขาต้องการสูตรที่จะให้ค่าประมาณของ R(k) แม้ — หรือโดยเฉพาะอย่างยิ่ง — เมื่อ k มีขนาดใหญ่มาก

"ฉันไม่รู้จักคนที่อยู่ใน combinatorics ที่ไม่ได้คิดถึงปัญหานี้เลยแม้แต่น้อย" วิกเดอร์สันกล่าว “ปัญหานี้ฉันคิดว่าพิเศษจริงๆ”

คำสั่งศาล

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

ห้าปีต่อมา Erdős และ Szekeres แสดงให้เห็นว่า Ramsey จำนวน k น้อยกว่า 4^k. และ 12 ปีหลังจากนั้น Erdősแสดงให้เห็น มันใหญ่กว่าประมาณ $latex sqrt{2}^k$ ในการทำเช่นนั้น เขาคำนวณโอกาสที่กราฟที่มีขอบสีแบบสุ่มจะมีกลุ่มสีเดียว เทคนิค "ความน่าจะเป็น" นี้มีอิทธิพลอย่างมากในทฤษฎีกราฟ มันยังขัง R(k) ระหว่างเสาประตูสองเสาที่กำลังเติบโตอย่างทวีคูณ: $latex sqrt{2}^k$ และ $latex 4^k$

เมื่อเวลาผ่านไปหลายทศวรรษ นักคณิตศาสตร์จำนวนมากพยายามลดช่องว่างระหว่างค่าที่เป็นไปได้ของจำนวนแรมซีย์ บางคนประสบความสำเร็จ: ในปี 1975 Joel Spencer เพิ่มขีด จำกัด ล่างเป็นสองเท่า. และชุดเอกสารโดย คอนลอน, แอนดรูว์ โธมัส และ อาชวิน ซาห์ ผลักขีดจำกัดบนลงมา โดยปัจจัยประมาณ $latex 4^{log(k)^2}$ ภายในปี 2020 แต่เมื่อเทียบกับขนาดของขอบเขตของหมายเลขแรมซีย์ การปรับเปลี่ยนเหล่านี้ถือว่าเล็กน้อย ในทางตรงกันข้าม การลดลงของ 4 ในสูตรของ Erdős และ Szekeres R(k) < 4^k จะเป็นการปรับปรุงแบบทวีคูณ เติบโตอย่างรวดเร็ว k ใหญ่ขึ้น

“ดูเหมือนจะเป็นคำถามเล็กๆ น้อยๆ ที่น่ารัก” กล่าว ร็อบ มอร์ริสนักคณิตศาสตร์ที่ IMPA สถาบันคณิตศาสตร์บริสุทธิ์และประยุกต์ของบราซิล ในเมืองรีโอเดจาเนโร ผู้ร่วมเขียนผลลัพธ์ใหม่กับ Campos, Griffiths และ Sahasrabudhe “มันเป็นเรื่องเล็กน้อยที่จะชื่นชม แต่ผู้คนสนใจมันจริงๆ” นี่อาจเป็นการพูดเกินจริง “หากพวกเขาพิสูจน์ได้ในปี 1936 ผู้คนคงจะพูดว่า ตกลง แล้วเรื่องใหญ่คืออะไร?” Béla Bollobás ซึ่งเป็นที่ปรึกษาระดับปริญญาเอกของ Morris และ Sahasrabudhe ที่มหาวิทยาลัยเมมฟิสกล่าว “ตั้งแต่นั้นมา มันก็ได้รับการพิสูจน์แล้วว่าเป็นปัญหาใหญ่มาก เพราะในช่วงหลายปีที่ผ่านมา มีการเขียนเอกสารหลายพันฉบับเกี่ยวกับปัญหาแรมซีย์ในรูปแบบต่างๆ” เช่น เลียน่า เยพรีเมียนนักคณิตศาสตร์แห่งมหาวิทยาลัยเอมอรีกล่าวว่า "ตัวเลขแรมซีย์สร้างสะพานเชื่อมระหว่างคอมบินาทอริกกับความน่าจะเป็นและเรขาคณิต"

ทฤษฎีเกม

 ในเดือนสิงหาคม พ.ศ. 2018 สหัสราบูเดเป็นเพื่อนร่วมงานหลังปริญญาเอกภายใต้สังกัดมอร์ริสที่ IMPA ทั้งสองหวังว่าจะเริ่มโครงการใหม่กับ Griffiths ซึ่งสอนอยู่ที่มหาวิทยาลัย Pontifical Catholic University ซึ่งอยู่ใกล้เคียง กระดาษโดย Conlon ดึงดูดความสนใจของพวกเขา กระดาษสรุปกลยุทธ์ที่เป็นไปได้สำหรับการปรับปรุงเลขแรมซีย์แบบทวีคูณ Griffiths, Morris และ Sahasrabudhe เริ่มเล่นกับแนวคิดนี้

“มันน่าตื่นเต้นจริงๆ ในตอนแรก” สหัสราบูเดเล่า พวกเขาใช้เวลาเพียงประมาณหนึ่งเดือน เขากล่าว เพื่อร่างร่างข้อโต้แย้งของพวกเขา

แผนของพวกเขาคือการสร้างแนวคิดที่ใช้ในการพิสูจน์ต้นฉบับของ Erdős และ Szekeres ว่า $latex R(k) < 4^k$ เพื่อพิสูจน์ว่าหมายเลขแรมซีย์มีค่าสูงสุดที่ $latex 4^k$ ลองจินตนาการว่าเล่นเกมบนกราฟที่สมบูรณ์ด้วยโหนด $latex 4^k$ เกมมีผู้เล่นสองคน ขั้นแรก คู่ต่อสู้ของคุณระบายสีขอบแต่ละด้านด้วยสีแดงหรือสีน้ำเงิน โดยหวังว่าจะลงสีขอบในลักษณะที่หลีกเลี่ยงการสร้างกลุ่มสีเดียวของ k โหนด

เมื่อคู่ต่อสู้ของคุณระบายสีเสร็จแล้ว หน้าที่ของคุณคือค้นหากลุ่มสีเดียว หากคุณพบคุณชนะ

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

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

ทำซ้ำจนกว่าคุณจะไม่มีโหนดเหลือ (เนื่องจากกราฟเสร็จสมบูรณ์ ทุกโหนดที่เหลือ ณ จุดใดๆ จะเชื่อมต่อกับที่เก็บข้อมูลทั้งสองจนกว่าจะวางลงในที่ใดที่หนึ่ง)

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

ข้อโต้แย้งนี้ฉลาดและสง่างาม แต่คุณต้องสร้างกลุ่มสองกลุ่ม – กลุ่มหนึ่งเป็นสีน้ำเงินและอีกกลุ่มเป็นสีแดง – แม้ว่าคุณต้องการเพียงกลุ่มเดียวจริงๆ มันจะมีประสิทธิภาพมากกว่าที่จะเป็นสีแดงเสมอ Conlon อธิบาย ภายใต้กลยุทธ์นี้ คุณจะต้องเลือกโหนดในแต่ละขั้นตอน ลบขอบสีน้ำเงิน และโยนลงในบัคเก็ตสีแดง ถังสีแดงจะเต็มอย่างรวดเร็ว และคุณก็จะสะสมกลุ่มสีแดง k โหนดในครึ่งเวลา

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

การสอบแบบเปิดหนังสือ

ในการอัปเดตรูปแบบการเล่นของพวกเขา Griffiths, Morris และ Sahasrabudhe เดินตามเส้นทางที่คดเคี้ยวกว่าเล็กน้อย แทนที่จะสร้างกลุ่มสีเดียวโดยตรงโดยการโยนโหนดในถังสีแดงและสีน้ำเงิน พวกเขามุ่งความสนใจไปที่การสร้างโครงสร้างที่เรียกว่าสมุดสีแดงก่อน

หนังสือในทฤษฎีกราฟประกอบด้วยสองส่วน: มีกลุ่มสีเดียวที่เรียกว่า "กระดูกสันหลัง" และกลุ่มที่สองที่แตกต่างกันของโหนดที่เรียกว่า "หน้า" ในสมุดปกแดง ขอบทั้งหมดที่เชื่อมต่อโหนดภายในสันจะเป็นสีแดง เช่นเดียวกับขอบที่เชื่อมสันเข้ากับหน้าต่างๆ อย่างไรก็ตาม ขอบที่เชื่อมต่อโหนดภายในหน้าสามารถเป็นสีใดก็ได้ Conlon ได้ระบุไว้ในเอกสารของเขาในปี 2018 ว่าหากคุณพบกลุ่มสีแดงในหน้าหนังสือ คุณสามารถรวมเข้ากับสันเพื่อให้ได้กลุ่มสีแดงที่ใหญ่ขึ้น วิธีนี้ช่วยให้คุณแบ่งการค้นหากลุ่มสีแดงขนาดใหญ่เป็นการค้นหาที่ง่ายขึ้นสองครั้ง ก่อนอื่นให้มองหาสมุดสีแดง จากนั้นมองหากลุ่มในหน้าของหนังสือ

Griffiths, Morris และ Sahasrabudhe ต้องการปรับอัลกอริธึมที่ชนะเกมเพื่อให้สร้าง Red Book แทนที่จะเป็นกลุ่ม Red แม้ว่าพวกเขาจะตกลงกับแผนนี้เพียงไม่กี่สัปดาห์ในโครงการของพวกเขา แต่ก็ต้องใช้เวลาหลายปีกว่าจะได้ผล พวกเขายังคงต้องป้องกันการคุกคามที่จะสูญเสียขอบสีแดงทั้งหมดไป

“เราติดอยู่เป็นเวลานานมาก” คัมโปสซึ่งเข้าร่วมโครงการในปี 2021 กล่าว

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

ตลอดมา ทีมมุ่งเน้นไปที่แรมซีย์หมายเลข R(k) หรือที่เรียกว่า "เส้นทแยงมุม" แรมซีย์นัมเบอร์ กราฟขนาด R(k) ต้องมี k โหนดทั้งหมดเชื่อมต่อกันด้วยขอบที่มีสีเดียวกัน แต่ไม่สำคัญว่าสีนั้นจะเป็นสีแดงหรือสีน้ำเงิน ในทางกลับกัน แรมซีย์หมายเลข R(k, l) วัดขนาดของกราฟก่อนที่จะมีกลุ่มสีแดงด้วย k โหนดหรือก๊กสีน้ำเงินด้วย l โหนด แทนที่จะเจาะปัญหาเส้นทแยงมุมต่อไป กลุ่มตัดสินใจลองใช้เวอร์ชันนอกเส้นทแยงมุม สิ่งนี้ได้รับการพิสูจน์แล้วว่าเป็นการเปิดเผย

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

จากนั้นนักคณิตศาสตร์ทั้งสี่คนใช้ขอบเขตใหม่บนหมายเลขแรมซีย์นอกแนวทแยงเพื่อเปิดทางสำหรับผลลัพธ์ในแนวทแยง เมื่อต้นเดือนกุมภาพันธ์ ในที่สุดพวกเขาก็ลดขีดจำกัดของจำนวนแรมซีย์ด้วยปัจจัยเลขชี้กำลัง ซึ่งเป็นความสำเร็จที่นักคณิตศาสตร์แสวงหามาเกือบศตวรรษ และพวกเขาทำได้โดยการปรับปรุงแนวข้อโต้แย้งเดียวกันกับที่ Erdős และ Szekeres นำเสนอในปี 1935 ให้ทันสมัย

เอปไซลอน, เอปไซลอน

หลังจากการพูดคุยเมื่อวันที่ 16 มีนาคม ผู้เข้าร่วมประชุมเริ่มยืนยันข่าวลือ รูปภาพจากการพูดคุยของสหัสราพุทธถูกเผยแพร่ผ่านทางโทรศัพท์และข้อความส่วนตัว แม้กระทั่งใน โพสต์คลุมเครือแต่ชี้นำ ในบล็อกของนักคณิตศาสตร์ Gil Kalai Campos, Griffiths, Sahasrabudhe และ Morris อ้างว่าได้แสดงให้เห็นว่า $latex R(k) < 3.993^k$ คืนนั้นผู้เขียนทั้งสี่ โพสต์กระดาษออนไลน์ทำให้นักคณิตศาสตร์ได้เห็นการพิสูจน์ใหม่ด้วยตนเอง

“ฉันคิดว่าพวกเราหลายคนไม่คาดคิดว่าชีวิตเราจะดีขึ้นเช่นนี้” กล่าว มาติยา บูซิชนักคณิตศาสตร์ที่ Princeton University และ Institute for Advanced Study “ฉันคิดว่ามันเป็นผลลัพธ์ที่น่าอัศจรรย์อย่างยิ่ง”

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

“มันเป็นข้อพิสูจน์ที่แยบยล ยอดเยี่ยม และเป็นความก้าวหน้าอย่างแท้จริง ตอนนี้ฉันคาดว่าประตูระบายน้ำจะเปิดแล้ว” Bollobás กล่าว “ผมมั่นใจว่าในเวลาสามปี การถกเถียงจะเกี่ยวกับการปรับปรุงที่เป็นไปได้ เราสามารถปรับปรุง 3.993 เป็น 3.9 ได้หรือไม่? อาจจะเป็น 3.4? แล้ว 3 ล่ะ?”

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

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