ใน 1850, โทมัส เพนนิ่งตัน เคิร์กแมนนักคณิตศาสตร์คนหนึ่งเมื่อเขาไม่ได้ทำหน้าที่หลักในฐานะบาทหลวงในนิกายเชิร์ชออฟอิงแลนด์ได้บรรลุถึง "ปัญหาของเด็กนักเรียนหญิง" ของเขาว่า: "หญิงสาวสิบห้าคนในโรงเรียนเดินออกไปสามคนติดต่อกันเจ็ดวัน: จำเป็นต้องจัดเตรียม ทุกวันเพื่อไม่ให้สองคนเดินเคียงคู่กัน”
สำหรับนักคณิตศาสตร์สมัยใหม่ ปัญหาประเภทนี้ควรจินตนาการว่าเป็นไฮเปอร์กราฟ ซึ่งเป็นชุดของโหนดที่รวบรวมเป็นกลุ่มตั้งแต่สามคนขึ้นไป เด็กนักเรียนหญิง 15 คนเป็นโหนด และแต่ละกลุ่มของ "สามคนที่อยู่ติดกัน" สามารถคิดได้ว่าเป็นสามเหลี่ยม โดยมีเส้นหรือขอบสามเส้นเชื่อมต่อกันสามโหนด
ปัญหาของเคิร์กแมนโดยพื้นฐานแล้วถามว่ามีการจัดเรียงของรูปสามเหลี่ยมเหล่านี้ที่เชื่อมนักเรียนหญิงทั้งหมดเข้าด้วยกันหรือไม่ แต่มีข้อจำกัดเพิ่มเติมว่าไม่มีรูปสามเหลี่ยมสองรูปที่แบ่งขอบ การแชร์ขอบจะบ่งบอกว่านักเรียนหญิงสองคนต้องเดินด้วยกันมากกว่าหนึ่งครั้ง ข้อจำกัดนี้หมายความว่าเด็กผู้หญิงแต่ละคนเดินกับเพื่อนใหม่สองคนทุกวันเป็นเวลาหนึ่งสัปดาห์ เพื่อให้ทุกคู่ที่เป็นไปได้มารวมกันเพียงครั้งเดียว
ปัญหานี้และปัญหาอื่นๆ ที่คล้ายคลึงกันได้หลอกล่อนักคณิตศาสตร์มาเกือบสองศตวรรษตั้งแต่เคิร์กแมนตั้งคำถาม ในปี 1973 นักคณิตศาสตร์ในตำนาน Paul Erdős ได้โพสท่าที่คล้ายกัน เขาถามว่าเป็นไปได้ไหมที่จะสร้างไฮเปอร์กราฟที่มีคุณสมบัติที่ดูเหมือนเข้ากันไม่ได้สองอย่าง อย่างแรก ทุกคู่ของโหนดจะต้องเชื่อมต่อกันด้วยสามเหลี่ยมเดียว เช่นเดียวกับเด็กนักเรียน คุณสมบัตินี้ทำให้กราฟหนาแน่นด้วยรูปสามเหลี่ยม ข้อกำหนดที่สองบังคับให้สามเหลี่ยมกระจายออกไปในลักษณะที่แม่นยำมาก (โดยเฉพาะอย่างยิ่ง จำเป็นต้องมีสำหรับกลุ่มสามเหลี่ยมเล็กๆ กลุ่มใดกลุ่มหนึ่ง ต้องมีโหนดมากกว่าสามเหลี่ยมอย่างน้อยสามโหนด) “คุณมีพฤติกรรมที่ขัดแย้งกันเล็กน้อยนี้ ซึ่งคุณมีวัตถุโดยรวมที่มีความหนาแน่นซึ่งไม่มีส่วนที่หนาแน่น” กล่าว เดวิด คอนลอนนักคณิตศาสตร์จากสถาบันเทคโนโลยีแคลิฟอร์เนีย
มกราคมนี้ใน หลักฐาน 50 หน้าที่ซับซ้อนนักคณิตศาสตร์สี่คนพิสูจน์แล้วว่าสามารถสร้างไฮเปอร์กราฟได้เสมอ ตราบใดที่คุณมีโหนดเพียงพอ “จำนวนเทคนิคที่ [พวกเขา] ผ่านเพื่อให้ได้สิ่งนี้ มันวิเศษมาก” . กล่าว อัลลัน โลนักคณิตศาสตร์จากมหาวิทยาลัยเบอร์มิงแฮม Conlon เห็นด้วย: “มันเป็นงานที่น่าประทับใจจริงๆ”
ทีมวิจัยได้สร้างระบบที่ตอบสนองความต้องการที่ชั่วร้ายของ Erdős โดยเริ่มจากกระบวนการสุ่มในการเลือกสามเหลี่ยมและวิศวกรรมด้วยความระมัดระวังอย่างยิ่งยวดเพื่อให้เหมาะกับความต้องการของพวกเขา Conlon กล่าวว่า "จำนวนการดัดแปลงที่ยากในการพิสูจน์นั้นเป็นเรื่องที่น่าสยดสยอง"
กลยุทธ์ของพวกเขาคือการสร้างไฮเปอร์กราฟจากสามเหลี่ยมแต่ละรูปอย่างระมัดระวัง ตัวอย่างเช่น ลองนึกภาพนักเรียนหญิง 15 คนของเรา ลากเส้นระหว่างแต่ละคู่
เป้าหมายในที่นี้คือการติดตามสามเหลี่ยมที่อยู่ด้านบนของเส้นเหล่านี้เพื่อให้สามเหลี่ยมตรงตามข้อกำหนดสองประการ: อันดับแรก ไม่มีสามเหลี่ยมสองรูปที่แบ่งขอบ (ระบบที่เป็นไปตามข้อกำหนดนี้เรียกว่าระบบสามชั้นของ Steiner) และประการที่สอง ตรวจสอบให้แน่ใจว่าชุดย่อยเล็กๆ ของรูปสามเหลี่ยมทุกชุดใช้โหนดจำนวนมากเพียงพอ
วิธีที่นักวิจัยทำสิ่งนี้อาจเข้าใจได้ดีที่สุดด้วยการเปรียบเทียบ
สมมติว่าแทนที่จะสร้างสามเหลี่ยมออกจากขอบ คุณกำลังสร้างบ้านจากอิฐเลโก้ อาคารสองสามหลังแรกที่คุณสร้างนั้นฟุ่มเฟือยด้วยการเสริมโครงสร้างและการประดับตกแต่งอย่างวิจิตรบรรจง เมื่อคุณทำสิ่งเหล่านี้เสร็จแล้ว ให้พักไว้ พวกเขาจะทำหน้าที่เป็น "ตัวดูดซับ" - ประเภทของคลังสินค้าที่มีโครงสร้าง
ตอนนี้เริ่มสร้างสิ่งปลูกสร้างจากอิฐที่เหลือของคุณ ดำเนินการโดยไม่ต้องวางแผนมาก เมื่ออุปทานเลโก้ของคุณลดน้อยลง คุณอาจพบว่าตัวเองมีอิฐหลงทางหรือบ้านที่มีโครงสร้างไม่แข็งแรง แต่เนื่องจากตัวดูดซับแรงเกินและเสริมแรงมาก คุณจึงสามารถดึงก้อนอิฐออกมาที่นี่และที่นั่นแล้วใช้งานโดยไม่ก่อให้เกิดภัยพิบัติ
ในกรณีของระบบสามชั้นของ Steiner คุณกำลังพยายามสร้างสามเหลี่ยม ในกรณีนี้ ตัวดูดซับของคุณคือคอลเล็กชันขอบที่เลือกสรรมาอย่างดี หากคุณพบว่าตัวเองไม่สามารถจัดเรียงส่วนที่เหลือของระบบให้เป็นรูปสามเหลี่ยมได้ คุณสามารถใช้ขอบบางส่วนที่นำไปสู่ตัวดูดซับ จากนั้น เมื่อคุณทำเสร็จแล้ว คุณจะแยกตัวดูดซับออกเป็นสามเหลี่ยม
การดูดซึมไม่ได้ผลเสมอไป แต่นักคณิตศาสตร์ได้แก้ไขกระบวนการนี้ และค้นหาวิธีใหม่ๆ ในการรับมือกับอุปสรรค ตัวอย่างเช่น ตัวแปรที่มีประสิทธิภาพที่เรียกว่า iterative absorption แบ่งขอบออกเป็นลำดับที่ซ้อนกันของชุด เพื่อให้แต่ละชุดทำหน้าที่เป็นตัวดูดซับสำหรับชุดที่ใหญ่ที่สุดถัดไป
“ในช่วงทศวรรษที่ผ่านมามีการปรับปรุงครั้งใหญ่” Conlon กล่าว “มันเป็นศิลปะอย่างหนึ่ง แต่พวกเขาได้นำมันมาสู่ระดับของศิลปะชั้นสูง ณ จุดนี้จริงๆ”
ปัญหาของ Erdő นั้นยากแม้จะดูดซับซ้ำๆ “มันค่อนข้างชัดเจนอย่างรวดเร็วว่าทำไมปัญหานี้ไม่ได้รับการแก้ไข” . กล่าว เมห์ตาบ ซอว์นีย์ซึ่งเป็นหนึ่งในสี่นักวิจัยที่แก้ปัญหานี้ร่วมกับ อาชวิน ซาห์ผู้ซึ่งร่วมกับซอว์นีย์เป็นนักศึกษาระดับบัณฑิตศึกษาที่สถาบันเทคโนโลยีแมสซาชูเซตส์ ไมเคิล ซิมกิ้น, เพื่อนดุษฎีบัณฑิตที่ศูนย์วิทยาศาสตร์คณิตศาสตร์และการประยุกต์ใช้ที่มหาวิทยาลัยฮาร์วาร์ด; และ แมทธิว ขวัญนักคณิตศาสตร์จากสถาบันวิทยาศาสตร์และเทคโนโลยีออสเตรีย “มีงานด้านเทคนิคที่ค่อนข้างน่าสนใจและค่อนข้างยาก”
ตัวอย่างเช่น ในการใช้งานอื่นๆ ของการดูดกลืนแบบวนซ้ำ เมื่อคุณครอบคลุมชุดครบแล้ว ไม่ว่าจะด้วยสามเหลี่ยม สำหรับระบบสามชั้นของ Steiner หรือกับโครงสร้างอื่นๆ สำหรับปัญหาอื่นๆ คุณสามารถพิจารณาว่ามันจัดการและลืมมันไปได้เลย อย่างไรก็ตาม เงื่อนไขของ Erdős ทำให้นักคณิตศาสตร์ทั้งสี่คนไม่สามารถทำเช่นนั้นได้ กลุ่มสามเหลี่ยมที่มีปัญหาอาจเกี่ยวข้องกับโหนดจากชุดตัวดูดซับหลายชุด
“สามเหลี่ยมที่คุณเลือกเมื่อ 500 ก้าวที่แล้ว คุณต้องจำวิธีคิดเกี่ยวกับสิ่งนั้นให้ได้” ซอว์นีย์กล่าว
สิ่งที่ทั้งสี่ค้นพบในที่สุดก็คือถ้าพวกเขาเลือกรูปสามเหลี่ยมอย่างระมัดระวัง พวกเขาสามารถหลีกเลี่ยงความจำเป็นในการติดตามทุกสิ่งเล็กน้อย "สิ่งที่ดีกว่าที่ควรทำคือคิดถึงชุดสามเหลี่ยมเล็กๆ 100 ชุด และรับประกันว่าชุดของสามเหลี่ยมจะถูกเลือกด้วยความน่าจะเป็นที่ถูกต้อง" Sawhney กล่าว
ผู้เขียนบทความใหม่มองโลกในแง่ดีว่าเทคนิคของพวกเขาสามารถขยายออกไปนอกเหนือจากปัญหาเดียว พวกเขามี ใช้กลยุทธ์ไปแล้ว เกี่ยวกับ สี่เหลี่ยมละตินซึ่งเหมือนกับการทำให้ปริศนาซูโดกุง่ายขึ้น
นอกจากนั้น ยังมีคำถามอีกหลายข้อที่อาจยอมจำนนต่อวิธีการดูดซึมในที่สุด ขวัญกล่าว "มีปัญหามากมายในวิทยาการเชิงผสม โดยเฉพาะอย่างยิ่งในทฤษฎีการออกแบบ ซึ่งกระบวนการสุ่มเป็นเครื่องมือที่ทรงพลังจริงๆ" ปัญหาดังกล่าวประการหนึ่ง การคาดเดาของ Ryser-Brualdi-Stein นั้นเกี่ยวกับจตุรัสละตินเช่นกันและได้รอคอยวิธีแก้ปัญหามาตั้งแต่ปี 1960
แม้ว่าการดูดซึมอาจต้องพัฒนาเพิ่มเติมก่อนที่จะสามารถขจัดปัญหานั้นได้ แต่ก็มาไกลตั้งแต่เริ่มก่อตั้งเมื่อ 30 ที่แล้ว .กล่าว มายา สไตน์รองผู้อำนวยการศูนย์การสร้างแบบจำลองทางคณิตศาสตร์ที่มหาวิทยาลัยชิลี “นั่นเป็นสิ่งที่ยอดเยี่ยมมากที่ได้เห็นวิธีการเหล่านี้พัฒนาขึ้น”
