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

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

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

การพิสูจน์โดยการอุปมานเกี่ยวกับขนาดของเซตที่มีลำดับบางส่วนต่อไปนี้มีพื้นฐานมาจากการพิสูจน์ของGalvin  ( 1994 ) ${\displaystyle P}$

ให้เป็นเซตจำกัดที่มีลำดับบางส่วน ทฤษฎีบทนี้เป็นจริงโดยปริยายถ้าเป็นเซตว่าง ดังนั้น สมมติว่ามีอย่างน้อยหนึ่งสมาชิก และให้เป็นสมาชิกสูงสุดของ ${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle a}$${\displaystyle P}$

โดยการอุปมาน เราสมมติว่าสำหรับจำนวนเต็มบางจำนวนเซตที่มีลำดับบางส่วนสามารถครอบคลุมได้ด้วยโซ่ที่ไม่ทับซ้อนกันและมีแอนติเชนอย่างน้อยหนึ่งอันที่มีขนาดเห็นได้ชัดว่าสำหรับสำหรับให้เป็นองค์ประกอบสูงสุดในที่อยู่ในแอนติเชนที่มีขนาดในและกำหนดเราอ้างว่าเป็นแอนติเชน ให้เป็นแอนติเชนที่มีขนาดที่ประกอบด้วยกำหนดดัชนีที่แตกต่างกันโดยพลการและแล้วให้แล้วโดยนิยามของซึ่งหมายความว่าเนื่องจากโดยการสลับบทบาทของและในอาร์กิวเมนต์นี้ เรายังมีซึ่งยืนยันว่าเป็นแอนติเชน ${\displaystyle k}$${\displaystyle P':=P\setminus \{a\}}$${\displaystyle k}$${\displaystyle C_{1},\dots ,C_{k}}$${\displaystyle A_{0}}$${\displaystyle k}$${\displaystyle A_{0}\cap C_{i}\neq \emptyset }$${\displaystyle i=1,2,\dots ,k}$${\displaystyle i=1,2,\dots ,k}$${\displaystyle x_{i}}$${\displaystyle C_{i}}$${\displaystyle k}$${\displaystyle P'}$${\displaystyle A:=\{x_{1},x_{2},\dots ,x_{k}\}}$${\displaystyle A}$${\displaystyle A_{i}}$${\displaystyle k}$${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle A_{i}\cap C_{j}\neq \emptyset }$${\displaystyle y\in A_{i}\cap C_{j}}$${\displaystyle y\leq x_{j}}$${\displaystyle x_{j}}$${\displaystyle x_{i}\not \geq x_{j}}$${\displaystyle x_{i}\not \geq y}$${\displaystyle i}$${\displaystyle j}$${\displaystyle x_{j}\not \geq x_{i}}$${\displaystyle A}$

ต่อไปนี้เราจะกลับมาพิจารณาอีกครั้ง สมมติก่อนว่าสำหรับบางค่าให้เป็นโซ่ แล้ว โดยการเลือกไม่มีแอนติเชนที่มีขนาดการอุปนัยจึงบ่งชี้ว่าสามารถครอบคลุมได้ด้วยโซ่ที่ไม่ทับซ้อนกัน เนื่องจากเป็นแอนติเชนที่มีขนาดในดังนั้นสามารถครอบคลุมได้ด้วยโซ่ที่ไม่ทับซ้อนกันตามที่ต้องการ ต่อไป ถ้าสำหรับแต่ละแล้วเป็นแอนติเชนที่มีขนาดใน(เนื่องจากมีค่าสูงสุดใน) ตอนนี้สามารถครอบคลุมได้ด้วยโซ่ซึ่งเป็นการเสร็จสิ้นการพิสูจน์ ${\displaystyle P}$${\displaystyle a\geq x_{i}}$${\displaystyle i\in \{1,2,\dots ,k\}}$${\displaystyle K}$${\displaystyle \{a\}\cup \{z\in C_{i}:z\leq x_{i}\}}$${\displaystyle x_{i}}$${\displaystyle P\setminus K}$${\displaystyle k}$${\displaystyle P\setminus K}$${\displaystyle k-1}$${\displaystyle A\setminus \{x_{i}\}}$${\displaystyle k-1}$${\displaystyle P\setminus K}$${\displaystyle P}$${\displaystyle k}$${\displaystyle a\not \geq x_{i}}$${\displaystyle i\in \{1,2,\dots ,k\}}$${\displaystyle A\cup \{a\}}$${\displaystyle k+1}$${\displaystyle P}$${\displaystyle a}$${\displaystyle P}$${\displaystyle P}$${\displaystyle k+1}$${\displaystyle \{a\},C_{1},C_{2},\dots ,C_{k}}$

^{เช่นเดียวกับผลลัพธ์อื่นๆ อีกหลายรายการในคณิตศาสตร์เชิงการจัด เรียง}ทฤษฎีบทของ Dilworth เทียบเท่ากับทฤษฎีบทของ Kőnigเกี่ยวกับ การจับคู่ กราฟสองส่วนและทฤษฎีบทอื่นๆ ที่เกี่ยวข้องอีกหลายรายการ รวมถึงทฤษฎีบทการแต่งงานของ Hall [ ^{2 ]}

เพื่อพิสูจน์ทฤษฎีบทของ Dilworth สำหรับลำดับบางส่วนSที่มีnสมาชิก โดยใช้ทฤษฎีบทของ Kőnig ให้กำหนดกราฟสองส่วนG = ( U , V , E ) โดยที่U = V = Sและ ( u , v ) เป็นขอบในGเมื่อu < vในSตามทฤษฎีบทของ Kőnig จะมีการจับคู่MในGและเซตของจุดยอดCในGซึ่งแต่ละขอบในกราฟมีจุดยอดอย่างน้อยหนึ่งจุดในC และ MกับCมีจำนวนสมาชิกเท่ากันคือmให้Aเป็นเซตของสมาชิกในSที่ไม่สอดคล้องกับจุดยอดใดๆ ในCแล้วAจะมีสมาชิกอย่างน้อยn - mตัว (อาจมากกว่านี้หากCมีจุดยอดที่สอดคล้องกับสมาชิกเดียวกันทั้งสองด้านของการแบ่งสองส่วน) และไม่มีสมาชิกสองตัวใดในAที่เปรียบเทียบกันได้ ให้Pเป็นกลุ่มของสายโซ่ที่เกิดจากการรวมxและyไว้ในสายโซ่เดียวกันเมื่อใดก็ตามที่มีขอบ ( x , y ) ในMดังนั้นPจะมี สายโซ่ n - mสาย ด้วยเหตุนี้ เราจึงได้สร้างแอนติเชนและพาร์ทิชันเป็นสายโซ่ที่มีจำนวนสมาชิกเท่ากัน

เพื่อพิสูจน์ทฤษฎีบทของ Kőnig จากทฤษฎีบทของ Dilworth สำหรับกราฟสองส่วนG = ( U , V , E ) ให้สร้างลำดับบางส่วนบนจุดยอดของGซึ่งu < vก็ต่อเมื่อuอยู่ในU , vอยู่ในVและมีขอบในEจากuไปยังvตามทฤษฎีบทของ Dilworth จะมีแอนติเชนAและพาร์ทิชันเป็นเชนPซึ่งทั้งสองมีขนาดเท่ากัน แต่เชนที่ไม่ใช่เชนว่างในลำดับบางส่วนมีเพียงคู่ขององค์ประกอบที่สอดคล้องกับขอบในกราฟ ดังนั้นเชนที่ไม่ใช่เชนว่างในPจึงก่อให้เกิดการจับคู่ในกราฟ ส่วนเติมเต็มของAก่อให้เกิดการปกคลุมจุดยอดในGที่มีขนาดเท่ากับการจับคู่นี้

การเชื่อมต่อกับการจับคู่แบบไบพาร์ไทต์นี้ทำให้สามารถคำนวณความกว้างของลำดับบางส่วนใดๆ ได้ในเวลาพหุนามกล่าวคือลำดับบางส่วนn องค์ประกอบที่มีความกว้าง kสามารถรับรู้ได้ในเวลาO ( kn ² ) ^{[ 3 ]}

ทฤษฎีบทของดิลเวิร์ธสำหรับเซตที่มีลำดับบางส่วนแบบอนันต์กล่าวว่า เซตที่มีลำดับบางส่วนจะมีค่าความกว้างจำกัดwก็ต่อเมื่อสามารถแบ่งออกเป็นwสายโซ่ได้ สมมติว่าลำดับบางส่วนแบบอนันต์Pมีค่าความกว้างwหมายความว่ามีจำนวนสมาชิก อย่างมากที่สุด w จำนวนในแอนติเชนใดๆ สำหรับเซตย่อย S ใดๆ ของPการแบ่งออกเป็นwสายโซ่ (ถ้ามี) สามารถอธิบายได้ว่าเป็นการระบายสีกราฟความไม่สามารถเปรียบเทียบกันได้ของS (กราฟที่มีสมาชิกของSเป็นจุดยอด โดยมีเส้นเชื่อมระหว่างสมาชิกที่ไม่สามารถเปรียบเทียบกันได้ทุกๆ สองตัว) โดยใช้ สี wสี แต่ละชั้นสีในการระบายสีกราฟความไม่สามารถเปรียบเทียบกันได้ที่เหมาะสมจะต้องเป็นสายโซ่ โดยสมมติฐานที่ว่าPมีค่าความกว้างwและโดยทฤษฎีบทของดิลเวิร์ธในเวอร์ชันจำกัด เซตย่อยจำกัดS ทุกเซต ของP จึง มี กราฟความไม่สามารถเปรียบเทียบกันได้ที่สามารถระบายสี ด้วย wสีได้ ดังนั้น ตามทฤษฎีบทของ De Bruijn–Erdősแล้วPเองก็มี กราฟที่ไม่สามารถเปรียบเทียบกันได้ซึ่งระบายสีด้วย wสี และด้วยเหตุนี้จึงมีการแบ่งส่วนที่ต้องการเป็นโซ่^{[ 4 ]}

อย่างไรก็ตาม ทฤษฎีบทนี้ไม่ได้ขยายไปถึงเซตที่มีลำดับบางส่วนซึ่งความกว้างและไม่ใช่แค่จำนวนสมาชิกของเซตเท่านั้นที่เป็นอนันต์ ในกรณีนี้ ขนาดของแอนติเชนที่ใหญ่ที่สุดและจำนวนเชนขั้นต่ำที่จำเป็นในการครอบคลุมลำดับบางส่วนอาจแตกต่างกันมาก โดยเฉพาะอย่างยิ่ง สำหรับจำนวนสมาชิกอนันต์ κ ทุกตัว จะมีเซตที่มีลำดับบางส่วนอนันต์ที่มีความกว้างℵ ₀ซึ่งการแบ่งส่วนออกเป็นเชนที่น้อยที่สุดจะมี κ เชน^{[ 4 ]}

Perles (1963)กล่าวถึงทฤษฎีบทที่คล้ายคลึงกับทฤษฎีบทของ Dilworth ในบริบทอนันต์

ทฤษฎีบทคู่ของ Dilworth ระบุว่าขนาดของโซ่ที่ใหญ่ที่สุดในลำดับบางส่วน (ถ้ามีจำนวนจำกัด) เท่ากับจำนวนแอนติเชนที่น้อยที่สุดที่สามารถแบ่งลำดับนั้นได้^{[ 5 ]}นี่เรียกว่าทฤษฎีบทของ Mirskyการพิสูจน์นั้นง่ายกว่าการพิสูจน์ทฤษฎีบทของ Dilworth มาก: สำหรับองค์ประกอบx ใดๆ ให้พิจารณาโซ่ที่มีxเป็นองค์ประกอบที่ใหญ่ที่สุด และให้N ( x ) แทนขนาดของ โซ่ x -maximal ที่ใหญ่ที่สุดเหล่านี้ จากนั้นแต่ละเซตN ⁻¹ ( i ) ซึ่งประกอบด้วยองค์ประกอบที่มีค่าN เท่ากัน จะเป็นแอนติเชน และแอนติเชนเหล่านี้จะแบ่งลำดับบางส่วนออกเป็นจำนวนแอนติเชนที่เท่ากับขนาดของโซ่ที่ใหญ่ที่สุด

กราฟเปรียบเทียบได้ (Comparability graph ) คือกราฟแบบไม่มีทิศทางที่สร้างขึ้นจากลำดับบางส่วน โดยการสร้างจุดยอดต่อองค์ประกอบแต่ละตัวในลำดับนั้น และสร้างเส้นเชื่อมระหว่างองค์ประกอบสองตัวใดๆ ที่สามารถเปรียบเทียบกันได้ ดังนั้น กลุ่มคลิก (clique)ในกราฟเปรียบเทียบได้จึงสอดคล้องกับโซ่ (chain) และเซตอิสระ (independent set)ในกราฟเปรียบเทียบได้จึงสอดคล้องกับแอนติเชน (antichain) กราฟย่อย ที่เกิดจากการเหนี่ยว นำ (induced subgraph)ของกราฟเปรียบเทียบได้นั้น ก็เป็นกราฟเปรียบเทียบได้เช่นกัน ซึ่งสร้างขึ้นจากการจำกัดลำดับบางส่วนให้เหลือเพียงเซตย่อยขององค์ประกอบเหล่านั้น

กราฟแบบไม่มีทิศทางจะสมบูรณ์แบบก็ต่อเมื่อในทุกกราฟย่อยที่เหนี่ยวนำจำนวนสีเท่ากับขนาดของคลิกที่ใหญ่ที่สุด กราฟเปรียบเทียบทุกกราฟจะสมบูรณ์แบบ: นี่เป็นเพียงทฤษฎีบทของ Mirsky ที่เขียนใหม่ในแง่ของทฤษฎีกราฟ^{[ 6 ]}ตามทฤษฎีบทกราฟสมบูรณ์แบบของLovász (1972)ส่วนเติมเต็มของกราฟสมบูรณ์แบบใดๆ ก็จะสมบูรณ์แบบเช่นกัน ดังนั้น ส่วนเติมเต็มของกราฟเปรียบเทียบใดๆ ก็จะสมบูรณ์แบบ นี่เป็นเพียงทฤษฎีบทของ Dilworth ที่เขียนใหม่ในแง่ของทฤษฎีกราฟ ( Berge & Chvátal 1984 ) ดังนั้น คุณสมบัติการเติมเต็มของกราฟสมบูรณ์แบบสามารถให้การพิสูจน์ทางเลือกของทฤษฎีบทของ Dilworth ได้

แลตทิซบูลีนB _nคือเซตกำลังของเซตX ที่มีสมาชิก n ตัว —โดยพื้นฐานแล้วคือ {1, 2, …, n }—เรียงลำดับตามการรวมหรือในเชิงสัญลักษณ์คือ (2 ^{[ n ]} , ⊆) ทฤษฎีบทของสเปอร์เนอร์กล่าวว่าแอนติเชนสูงสุดของB _nมีขนาดไม่เกิน

${\displaystyle \operatorname {width} (B_{n})={n \choose \lfloor {n/2}\rfloor }.}$

กล่าวอีกนัยหนึ่งคือ กลุ่มย่อยที่ไม่สามารถเปรียบเทียบกันได้ที่ใหญ่ที่สุดของXได้มาจากการเลือกกลุ่มย่อยของXที่มีขนาดมัธยฐาน อสมการ ของ Lubell–Yamamoto–Meshalkinยังเกี่ยวข้องกับแอนติเชนในเซตกำลัง และสามารถใช้พิสูจน์ทฤษฎีบทของ Sperner ได้

ถ้าเราเรียงลำดับจำนวนเต็มในช่วง [1, 2n ]ตามการหารลงตัวช่วงย่อย [ n  + 1, 2n ]จะก่อให้เกิดแอนติเชนที่มีขนาดⁿการแบ่งลำดับบางส่วนนี้ออกเป็นnเชนทำได้ง่าย: สำหรับจำนวนเต็มคี่m แต่ละตัว ในช่วง [1, 2n ] ให้สร้างเชนของจำนวนในรูปแบบm 2i ดังนั้น ตามทฤษฎีบทของดิลเวิร์ธ ความกว้างของลำดับบางส่วนนี้คือ n

ทฤษฎีบท Erdős –Szekeresเกี่ยวกับลำดับย่อยโมโนโทนสามารถตีความได้ว่าเป็นการประยุกต์ใช้ทฤษฎีบทของ Dilworth กับลำดับย่อยที่มีมิติลำดับสอง^{[ 7 ]}

"มิตินูน" ของแอนติแมทรอยด์ถูกกำหนดให้เป็นจำนวนโซ่ขั้นต่ำที่จำเป็นในการกำหนดแอนติแมทรอยด์ และทฤษฎีบทของดิลเวิร์ธสามารถใช้เพื่อแสดงว่ามันเท่ากับความกว้างของลำดับบางส่วนที่เกี่ยวข้อง การเชื่อมต่อนี้นำไปสู่อัลกอริทึมเวลาพหุนามสำหรับมิตินูน^{[ 8 ]}

• Robert D. Borgersen (26 พฤศจิกายน 2004), ความเท่าเทียมกันของทฤษฎีบทหลักเจ็ดข้อในคณิตศาสตร์เชิงการจัดเรียง (PDF) , เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 21 กรกฎาคม 2011
• ทฤษฎีบทคู่ของดิลเวิร์ธที่PlanetMath
• Babai, László (2005), Lecture Notes in Combinatorics and Probability, Lecture 10: Perfect Graphs (PDF) , เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2011-07-20
• Felsner, S.; Raghavan, V. & Spinrad, J. (1999), อัลกอริทึมการจำแนกสำหรับลำดับที่มีความกว้างน้อยและกราฟที่มีเลขดิลเวิร์ธขนาดเล็ก
• ไวส์สไตน์, เอริค ดับเบิลยู. "ทฤษฎีบทเสริมของดิลเวิร์ธ" . แมธเวิลด์ .