ในคณิตศาสตร์เชิงการ จัดเรียง ทฤษฎีบทDinitz ⁽เดิมเรียกว่าสมมติฐาน Dinitz ) เป็นข้อความเกี่ยวกับการขยายอาร์เรย์ไปยังตารางละติน บางส่วน ซึ่งเสนอโดย Jeff Dinitzในปี 1979 [ ^{1 ]}และพิสูจน์โดยFred Galvinใน ปี 1994 ^{[ 2 ] [ 3 ]}

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

การพิสูจน์ของ Galvin ขยายไปสู่ข้อความที่ว่า สำหรับมัลติกราฟ แบบสองส่วนทุกอัน ดัชนีสีรายการจะเท่ากับดัชนีสีรายการ ของมัน ข้อสันนิษฐานการระบายสีขอบรายการที่ทั่วไปกว่านั้นระบุว่าสิ่งเดียวกันนี้ไม่เพียงแต่ใช้ได้กับกราฟแบบสองส่วนเท่านั้น แต่ยังใช้ได้กับมัลติกราฟที่ไม่มีวงวนอีกด้วย ข้อสันนิษฐานที่ทั่วไปกว่านั้นระบุว่าจำนวนสีรายการของกราฟที่ไม่มีกรงเล็บจะ เท่ากับ จำนวนสีรายการของมันเสมอ^{[ 4 ]}ทฤษฎีบท Dinitz ยังเกี่ยวข้องกับ ข้อ สันนิษฐานฐานของ Rota อีกด้วย ^{[ 5 ]}

• ไวส์สไตน์, เอริก ดับเบิลยู. "ปัญหาดินิทซ์" . แมทเวิลด์ .

บทความเกี่ยวกับทฤษฎีกราฟนี้ ยัง ไม่สมบูรณ์คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มข้อมูลที่ขาดหายไป

• วี
• ที
• อี