ปัญหาที่ยังแก้ไม่ได้ในวิชาคณิตศาสตร์

สำหรับ 2-ปกติ${\displaystyle n}$กราฟจุดยอด${\displaystyle G}$กราฟที่สมบูรณ์สามารถ${\displaystyle K_{n}}$จะถูกแยกออกเป็นสำเนาที่ไม่ทับซ้อนกันของขอบ${\displaystyle G}$?

ปัญหาที่ยังแก้ไม่ตกในวิชาคณิตศาสตร์ยังมีอีกมากมาย

ในทางคณิตศาสตร์ปัญหาโอเบอร์โวล์ฟัคเป็นปัญหาที่ยังเปิดอยู่ซึ่งอาจกำหนดได้เป็นปัญหาเกี่ยวกับการจัดตารางที่นั่งสำหรับผู้รับประทานอาหาร หรือในเชิงนามธรรมมากขึ้นในฐานะปัญหาในทฤษฎีกราฟเกี่ยวกับการครอบคลุมวงจรขอบของกราฟสมบูรณ์ปัญหานี้ตั้งชื่อตามสถาบันวิจัยคณิตศาสตร์โอเบอร์โว ล์ฟัค ซึ่งปัญหาดังกล่าวถูกตั้งขึ้นในปี 1967 โดยเกอร์ฮาร์ด ริงเกล^{[ 1 ]}เป็นที่ทราบกันว่าเป็นจริงสำหรับกราฟสมบูรณ์ขนาดใหญ่ทั้งหมด

ในการประชุมที่จัดขึ้นที่โอเบอร์โวล์ฟัค เป็นธรรมเนียมที่ผู้เข้าร่วมประชุมจะรับประทานอาหารร่วมกันในห้องที่มีโต๊ะกลม ซึ่งขนาดไม่เท่ากันทั้งหมด และมีการจัดที่นั่งที่เปลี่ยนแปลงไปในแต่ละมื้อ ปัญหาโอเบอร์โวล์ฟัคถามว่า จะจัดแผนผังที่นั่งสำหรับโต๊ะชุดหนึ่งอย่างไร เพื่อให้โต๊ะทุกโต๊ะเต็มในทุกมื้อ และผู้เข้าร่วมประชุมทุกคู่ได้นั่งติดกันเพียงครั้งเดียวเท่านั้น ตัวอย่างของปัญหานี้สามารถแสดงได้ดังนี้${\displaystyle OP(x,y,z,\dots )}$ที่ไหน${\displaystyle x,y,z,\dots }$คือขนาดของตารางที่กำหนดไว้ หรืออีกทางหนึ่ง เมื่อขนาดของตารางบางขนาดซ้ำกัน อาจใช้สัญลักษณ์เลขยกกำลังแทนได้ เช่น${\displaystyle OP(5^{3})}$อธิบายอินสแตนซ์ที่มีตารางสามตารางขนาดห้าตาราง^{[ 1 ]}

เมื่อกำหนดเป็นปัญหาในทฤษฎีกราฟ คู่ของคนที่นั่งติดกันในมื้ออาหารเดียวกันสามารถแทนได้ด้วยการรวมกันแบบไม่ทับซ้อนกันของกราฟวงจร${\displaystyle C_{x}+C_{y}+C_{z}+\cdots }$โดยมีความยาวตามที่กำหนด และมีหนึ่งวงจรสำหรับโต๊ะรับประทานอาหารแต่ละโต๊ะ การรวมกันของวงจรเหล่านี้เป็น กราฟ ปกติ 2 มิติ และ กราฟ ปกติ 2 มิติ ทุก กราฟจะมีรูปแบบนี้ ถ้า${\displaystyle G}$นี่คือ กราฟ ปกติ 2 มิติและมี${\displaystyle n}$จุดยอด คำถามคือว่ากราฟสมบูรณ์หรือไม่${\displaystyle K_{n}}$ของคำสั่ง${\displaystyle n}$สามารถแสดงได้ในรูปของการรวมกันแบบไม่ทับซ้อนกันของขอบของสำเนาต่างๆ${\displaystyle G}$[ ^{1 ]​}

เพื่อให้มีคำตอบได้ จำนวนผู้เข้าร่วมประชุมทั้งหมด (หรือเทียบเท่ากับความจุรวมของโต๊ะ หรือจำนวนจุดยอดรวมของกราฟวงจรที่กำหนด) ต้องเป็นจำนวนคี่ เนื่องจากในแต่ละมื้ออาหาร ผู้เข้าร่วมแต่ละคนจะนั่งข้างเพื่อนบ้านสองคน ดังนั้นจำนวนเพื่อนบ้านทั้งหมดของผู้เข้าร่วมแต่ละคนต้องเป็นจำนวนคู่ และสิ่งนี้จะเป็นไปได้ก็ต่อเมื่อจำนวนผู้เข้าร่วมทั้งหมดเป็นจำนวนคี่เท่านั้น อย่างไรก็ตาม ปัญหานี้ได้รับการขยายไปยังค่าคู่ของจำนวนผู้เข้าร่วมด้วยเช่นกัน${\displaystyle n}$โดยการถาม สำหรับคนเหล่านั้น${\displaystyle n}$ว่าขอบทั้งหมดของกราฟสมบูรณ์ ยกเว้นการจับคู่ที่สมบูรณ์แบบสามารถถูกครอบคลุมโดยสำเนาของ กราฟ 2-ปกติ ที่กำหนดให้ได้ หรือไม่ เช่นเดียวกับปัญหาเมเนจ (ปัญหาทางคณิตศาสตร์อีกแบบหนึ่งที่เกี่ยวข้องกับการจัดที่นั่งของผู้รับประทานอาหารและโต๊ะ) รูปแบบหนึ่งของปัญหานี้สามารถกำหนดได้โดยการสมมติว่า${\displaystyle n}$ผู้รับประทานอาหารจะถูกจัดเรียงเป็นกลุ่มๆ${\displaystyle n/2}$คู่สมรส และการจัดที่นั่งควรให้ผู้รับประทานอาหารแต่ละคนนั่งติดกัน ยกเว้นคู่สมรสของตนเองเพียงครั้งเดียว^{[ 2 ]}

Glock, Joos, Kim, Kühn และ Osthus ^{[ 3 ]}พบวิธีแก้ปัญหาสำหรับกรณีส่วนใหญ่ของปัญหา Oberwolfach ยกเว้นเพียงจำนวนจำกัด เป็นที่ทราบกันว่าสำหรับ${\displaystyle OP(3^{2})}$,${\displaystyle OP(3^{4})}$,${\displaystyle OP(4,5)}$, และ${\displaystyle OP(3,3,5)}$ไม่มีวิธีแก้ปัญหาที่เป็นไปได้^{[ 4 ]}และเป็นที่เชื่อกันอย่างกว้างขวางว่ากรณีอื่นๆ ทั้งหมดมีวิธีแก้ปัญหา

การแก้ปัญหาสำหรับจำนวนจุดยอดจำนวนมากนั้นเกี่ยวข้องกับขั้นตอนแบบสุ่มหลายขั้นตอน กรณีที่ทราบวิธีการแก้ปัญหาแบบสร้างสรรค์ ได้แก่:

• ทุกกรณี${\displaystyle OP(x^{y})}$ยกเว้น${\displaystyle OP(3^{2})}$และ${\displaystyle OP(3^{4})}$[ ^{5 ] [ 6 ] [ 7 ] [ 8 ] [ 2 ]​}
• กรณีทั้งหมดที่วัฏจักรทั้งหมดมีความยาวเท่ากัน^{[ 5 ] [ 9 ]}
• กรณีทั้งหมด (นอกเหนือจากข้อยกเว้นที่ทราบแล้ว) ที่มี${\displaystyle n\leq 60}$[ ^{10 ] [ 4 ]​}
• กรณีทั้งหมดสำหรับตัวเลือกบางอย่างของ${\displaystyle n}$ซึ่งเป็นเซตย่อยอนันต์ของจำนวนธรรมชาติ^{[ 11 ] [ 12 ]}
• ทุกกรณี${\displaystyle OP(x,y)}$นอกเหนือจากข้อยกเว้นที่ทราบแล้ว${\displaystyle OP(3,3)}$และ${\displaystyle OP(4,5)}$[ ^{13 ]​}

Glock, Kühn และ Osthus ^{[ 14 ]}เสนอการวางนัยทั่วไปของปัญหา Oberwolfach สำหรับ${\displaystyle k}$- ไฮเปอร์กราฟแบบสม่ำเสมอ(สำหรับขนาดใหญ่)${\displaystyle n}$)

ปัญหาที่ยังแก้ไม่ได้ในวิชาคณิตศาสตร์

สมมติ${\displaystyle n}$แบ่งแยก${\displaystyle {\tbinom {n}{k}}}$และปล่อยให้${\displaystyle F}$เป็น${\displaystyle n}$-กราฟจุดยอด ซึ่งเป็นการรวมกันแบบไม่ทับซ้อนกันของวงจรแน่นที่มีความยาวอย่างน้อย${\displaystyle 2k+1}$. แล้ว${\displaystyle K_{n}^{(k)}}$สามารถแยกย่อยออกเป็นสำเนาของ${\displaystyle F}$.

ปัญหาที่ยังแก้ไม่ตกในวิชาคณิตศาสตร์ยังมีอีกมากมาย

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

ปัญหาของเคิร์กแมนเกี่ยวกับการจัดกลุ่มนักเรียนหญิง 15 คนเป็นแถวละสามคนในเจ็ดวิธีที่แตกต่างกัน โดยที่นักเรียนหญิงแต่ละคู่ปรากฏเพียงครั้งเดียวในแต่ละกลุ่มสามคนนั้น เป็นกรณีพิเศษของปัญหาโอเบอร์โวล์ฟัค${\displaystyle OP(3^{5})}$ปัญหาการแยกส่วนแฮมิลโทเนียนของกราฟสมบูรณ์${\displaystyle K_{n}}$นี่เป็นกรณีพิเศษอีกกรณีหนึ่ง${\displaystyle OP(n)}$[ ^{9 ]​}

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