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

ผลลัพธ์นี้บางครั้งเรียกว่าทฤษฎีบทของสเปอร์เนอร์ (Sperner's lemma) แต่ชื่อ " ทฤษฎีบทของสเปอร์เนอร์ " ยังหมายถึงผลลัพธ์ที่ไม่เกี่ยวข้องอีกอย่างหนึ่งเกี่ยวกับการระบายสีรูปสามเหลี่ยมด้วย เพื่อแยกแยะผลลัพธ์ทั้งสอง ผลลัพธ์เกี่ยวกับขนาดของตระกูลสเปอร์เนอร์จึงมักถูกเรียกว่าทฤษฎีบทของสเปอร์เนอร์ (Sperner's theorem) มากกว่าในปัจจุบัน

กลุ่มของเซตที่ไม่มีเซตใดเป็นเซตย่อยโดยแท้จริงของเซตอื่น เรียกว่ากลุ่มของเซตสเปอร์เนอร์หรือแอนติเชนของเซต หรือ คลัตเตอร์ ตัวอย่างเช่น กลุ่มของ เซตย่อยที่มี kสมาชิกของ เซตที่มี nสมาชิก เป็นกลุ่มของเซตสเปอร์เนอร์ ไม่มีเซตใดในกลุ่มนี้ที่สามารถบรรจุเซตอื่นได้ เพราะเซตที่บรรจุจะต้องมีขนาดใหญ่กว่าเซตที่มันบรรจุโดยแท้จริง และในกลุ่มนี้ เซตทั้งหมดมีขนาดเท่ากัน ค่าของkที่ทำให้ตัวอย่างนี้มีจำนวนเซตมากที่สุดคือn /2 ถ้าnเป็นจำนวนคู่ หรือจำนวนเต็มที่ใกล้เคียงที่สุดกับn /2 ถ้าnเป็นจำนวนคี่ สำหรับค่านี้ จำนวนเซตในกลุ่มคือ... ${\displaystyle {\tbinom {n}{\lfloor n/2\rfloor }}}$

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

1. สำหรับทุกตระกูลสเปอร์เนอร์S ที่ผลรวมของตระกูลนั้นมี สมาชิกทั้งหมดn ตัว และ${\displaystyle |S|\leq {\binom {n}{\lfloor n/2\rfloor }},}$
2. ความเท่าเทียมกันจะเป็นจริงก็ต่อเมื่อSประกอบด้วยเซตย่อยทั้งหมดของ เซตที่มีสมาชิก nตัว ซึ่งมีขนาดหรือเซตย่อยทั้งหมดที่มีขนาด${\displaystyle \lfloor n/2\rfloor }$${\displaystyle \lceil n/2\rceil }$

ทฤษฎีบทของสเปอร์เนอร์สามารถกล่าวได้ในแง่ของความกว้างของลำดับบางส่วนได้เช่นกัน ตระกูลของเซตย่อยทั้งหมดของ เซตที่มีสมาชิก nตัว ( เซตกำลัง ของมัน ) สามารถเรียงลำดับได้บางส่วนโดยการรวมเซต ในลำดับบางส่วนนี้ สมาชิกสองตัวที่แตกต่างกันจะกล่าวได้ว่าเปรียบเทียบกันไม่ได้เมื่อไม่มีสมาชิกใดบรรจุอีกสมาชิกหนึ่ง ความกว้างของลำดับบางส่วนคือจำนวนสมาชิกที่มากที่สุดในแอนติเชนซึ่งเป็นเซตของสมาชิกที่เปรียบเทียบกันไม่ได้เป็นคู่ๆ เมื่อแปลศัพท์นี้เป็นภาษาของเซต แอนติเชนก็คือตระกูลสเปอร์เนอร์ และความกว้างของลำดับบางส่วนคือจำนวนเซตสูงสุดในตระกูลสเปอร์เนอร์ ดังนั้น อีกวิธีหนึ่งในการกล่าวถึงทฤษฎีบทของสเปอร์เนอร์คือ ความกว้างของลำดับการรวมบนเซตกำลังคือ ${\displaystyle {\binom {n}{\lfloor n/2\rfloor }}}$

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

มีบทพิสูจน์มากมายของทฤษฎีบทของสเปอร์เนอร์ ซึ่งแต่ละบทพิสูจน์นำไปสู่การสรุปทั่วไปที่แตกต่างกัน (ดูAnderson (1987) )

บทพิสูจน์ต่อไปนี้เป็นผลงานของLubell (1966)ให้s แทนจำนวน เซต kในSสำหรับทุก 0 ≤ k ≤ n

${\displaystyle {n \choose \lfloor {n/2}\rfloor }\geq {n \choose k}}$

และด้วยเหตุนี้

${\displaystyle {s_{k} \over {n \choose \lfloor {n/2}\rfloor }}\leq {s_{k} \over {n \choose k}}.}$

เนื่องจากSเป็นแอนติเชน เราจึงสามารถรวมผลรวมของอสมการข้างต้นจากk = 0 ถึงnแล้วใช้อสมการ LYMเพื่อให้ได้

${\displaystyle \sum _{k=0}^{n}{s_{k} \over {n \choose \lfloor {n/2}\rfloor }}\leq \sum _{k=0}^{n}{s_{k} \over {n \choose k}}\leq 1,}$

ซึ่งหมายความว่า

${\displaystyle |S|=\sum _{k=0}^{n}s_{k}\leq {n \choose \lfloor {n/2}\rfloor }.}$

การพิสูจน์ส่วนที่ 1 เสร็จสมบูรณ์แล้ว

เพื่อให้เกิดความเท่าเทียมกัน อสมการทั้งหมดในบทพิสูจน์ก่อนหน้านี้จะต้องกลายเป็นสมการ เนื่องจาก

${\displaystyle {n \choose \lfloor {n/2}\rfloor }={n \choose k}}$

ก็ต่อเมื่อหรือเราสรุปได้ว่าความเท่าเทียมกันหมายความว่าSประกอบด้วยเซตที่มีขนาดหรือ เท่านั้น สำหรับn ที่เป็นเลขคู่ ซึ่งเป็นการสรุปการพิสูจน์ส่วนที่ 2 ${\displaystyle k=\lfloor {n/2}\rfloor }$${\displaystyle \lceil {n/2}\rceil ,}$${\displaystyle \lfloor {n/2}\rfloor }$${\displaystyle \lceil {n/2}\rceil .}$

สำหรับn ที่เป็นเลขคี่ จะมีงานที่ต้องทำเพิ่มเติม ซึ่งเราจะละเว้นไว้ในที่นี้เนื่องจากมีความซับซ้อน โปรดดูAnderson (1987)หน้า 3–4

มีการขยายความทั่วไปหลายประการของทฤษฎีบทของสเปอร์เนอร์สำหรับเซตย่อยของโพเซตของเซตย่อยทั้งหมดของ E${\displaystyle {\mathcal {P}}(E),}$

โซ่(Chain)คือกลุ่มย่อยที่มีลำดับสมบูรณ์ กล่าวคือ(อาจหลังจากการจัดลำดับใหม่) โซ่นี้มีสมาชิกr + 1 ตัว และ มีความยาวrกลุ่มที่ไม่มีโซ่r ตัว (เรียกอีกอย่างว่า กลุ่มr -family ) คือกลุ่มของเซตย่อยของEที่ไม่มีโซ่ที่มีความยาวrตัว Erdős (1945)พิสูจน์ว่าขนาดที่ใหญ่ที่สุดของ กลุ่มที่ไม่มีโซ่ rตัว คือผลรวมของสัมประสิทธิ์ทวินามที่ใหญ่ที่สุดrตัว กรณีr = 1 คือทฤษฎีบทของ Sperner ${\displaystyle \{S_{0},S_{1},\dots ,S_{r}\}\subseteq {\mathcal {P}}(E)}$${\displaystyle S_{0}\subset S_{1}\subset \dots \subset S_{r}}$${\displaystyle {\binom {n}{i}}}$

ในเซตของp -tuple ของเซตย่อยของEเรากล่าวว่าp -tuple หนึ่ง ≤ อีก p-tuple หนึ่งถ้าสำหรับแต่ละi = 1,2,..., pเราเรียก เซต เหล่า นั้น ว่า p -composition ของEถ้าเซตเหล่านั้นก่อให้เกิดการแบ่งส่วนของE เมชาลกิน (1963)พิสูจน์ว่าขนาดสูงสุดของ antichain ของp -composition คือ สัมประสิทธิ์p -multinomial ที่ใหญ่ที่สุดนั่นคือสัมประสิทธิ์ที่n ทั้งหมด ใกล้เคียงกันมากที่สุดเท่าที่จะเป็นไปได้ (กล่าวคือ ต่างกันไม่เกิน 1) เมชาลกินพิสูจน์สิ่งนี้โดยการพิสูจน์อสมการ LYM แบบทั่วไป ${\displaystyle {\คณิตศาสตร์ {P}}(E)^{p}}$${\displaystyle (S_{1},\dots ,S_{p})}$${\displaystyle (T_{1},\dots ,T_{p}),}$${\displaystyle S_{i}\subseteq T_{i}}$${\displaystyle (S_{1},\dots ,S_{p})}$${\displaystyle S_{1},\dots ,S_{p}}$${\displaystyle {\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},}$

กรณีp = 2 คือทฤษฎีบทของสเปอร์เนอร์ เพราะในกรณีนั้นและข้อสมมติจะลดลงเหลือเพียงเซตที่เป็นตระกูลสเปอร์เนอร์ ${\displaystyle S_{2}=E\setminus S_{1}}$${\displaystyle S_{1}}$

Beck & Zaslavsky (2002)ได้รวมทฤษฎีบทของ Erdös และ Meshalkin เข้าด้วยกันโดยปรับใช้การพิสูจน์อสมการ LYM ทั่วไปของ Meshalkin พวกเขาแสดงให้เห็นว่าขนาดที่ใหญ่ที่สุดของกลุ่มp -composition ที่ทำให้เซตใน ตำแหน่ง ที่ iของp -tuple โดยไม่คำนึงถึงการซ้ำซ้อนนั้น ปราศจาก r -chain สำหรับทุก ๆ(แต่ไม่จำเป็นสำหรับi = p ) จะไม่มากกว่าผลรวมของสัมประสิทธิ์ p -multinomial ที่ใหญ่ที่สุด${\displaystyle i=1,2,\dots ,p-1}$${\displaystyle r^{p-1}}$

ในเรขาคณิตเชิงโปรเจกทีฟ จำกัด PG( d , F ) ที่มีมิติdเหนือฟิลด์จำกัดที่มีอันดับqให้เป็นตระกูลของปริภูมิย่อยทั้งหมด เมื่อเรียงลำดับบางส่วนโดยการรวมเซต ตระกูลนี้จะเป็นแลตทิซ Rota & Harper (1971)พิสูจน์ว่าขนาดที่ใหญ่ที่สุดของแอนติเชนในคือสัมประสิทธิ์เกาส์เซียน ที่ใหญ่ที่สุด นี่คืออนาล็อกทางเรขาคณิตเชิงโปรเจกทีฟ หรืออนาล็อกqของทฤษฎีบทของสเปอร์เนอร์ ${\displaystyle {\mathcal {L}}(p,F_{q})}$${\displaystyle {\mathcal {L}}(p,F_{q})}$${\displaystyle {\begin{bmatrix}d+1\\k\end{bmatrix}};}$

นอกจากนี้ พวกเขายังพิสูจน์ได้ว่าขนาดที่ใหญ่ที่สุดของ กลุ่ม r -chain-free ในคือผลรวมของ สัมประสิทธิ์เกาส์เซียนที่ใหญ่ที่สุด rตัว การพิสูจน์ของพวกเขานั้นใช้การเปรียบเทียบเชิงโปรเจคทีฟของอสมการ LYM ${\displaystyle {\mathcal {L}}(p,F_{q})}$

Beck & Zaslavsky (2003)ได้รับการวางนัยทั่วไปแบบ Meshalkin ของทฤษฎีบท Rota–Harper ใน PG( d , Fq ) ลำดับ Meshalkinที่มีความยาวpคือลำดับ ของปริภูมิย่อยเชิงโปรเจก ฟซึ่งไม่มีปริภูมิย่อยแท้ใดของ PG( d , Fq ที่ครอบคลุมปริภูมิย่อยเหล่านั้นทั้งหมด และผลรวมของมิติของปริภูมิย่อยเหล่านั้นเท่ากับทฤษฎีบทกล่าวว่าตระกูลของลำดับ Meshalkin ที่มีความยาวpใน PG( d , Fq ซึ่งปริภูมิย่อยที่ปรากฏในตำแหน่งiของลำดับนั้นไม่มีสายโซ่ที่มีความยาวrสำหรับแต่ละลำดับนั้นจะไม่เกินผลรวมของปริมาณที่มากที่สุดของปริมาณ ${\displaystyle (A_{1},\ldots ,A_{p})}$${\displaystyle d-p+1}$${\displaystyle i=1,2,\dots ,p-1,}$${\displaystyle r^{p-1}}$

${\displaystyle {\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}q^{s_{2}(n_{1},\ldots ,n_{p})},}$

โดยที่(ซึ่งเราสมมติว่า) หมายถึง สัมประสิทธิ์ p -Gaussian ${\displaystyle {\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}}$${\displaystyle d+1=n_{1}+\cdots +n_{p}}$

${\displaystyle {\begin{bmatrix}d+1\\n_{1}\end{bmatrix}}{\begin{bmatrix}d+1-n_{1}\\n_{2}\end{bmatrix}}\cdots {\begin{bmatrix}d+1-(n_{1}+\cdots +n_{p-1})\\n_{p}\end{bmatrix}}}$

และ

${\displaystyle s_{2}(n_{1},\ldots ,n_{p}):=n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3}+n_{1}n_{4}+\cdots +n_{p-1}n_{p},}$

ฟังก์ชันสมมาตรพื้นฐานที่สองของตัวเลข${\displaystyle n_{1},n_{2},\dots ,n_{p}.}$

• ทฤษฎีบทของดิลเวิร์ธ
• ทฤษฎีบท Erdős–Ko–Rado

• ทฤษฎีบทของสเปอร์เนอร์ที่cut-the-knot
• ทฤษฎีบทของสเปอร์เนอร์ในวิกิ polymath1