Teorema de Sperner

En matemàtica discreta, la teorema de Sperner descriu les majors famílies possibles d'un conjunt finito, cap de les quals conté atres conjunts de la família. És un dels resultats centrals de la teoria de conjunts d'extrems. Rep el seu nom en honor a Emanuel Sperner, qui ho va publicar en 1928.

Este resultat a voltes es denomina lema de Sperner, pero el nom lema de Sperner també es referix a un resultat no relacionat sobre la coloració de triangulacions. Per a diferenciar abdós resultats, el resultat sobre el tamany d'una família de Sperner es coneix ara més comunament com a teorema de Sperner.

Enunciat

Una família de conjunts en la que cap dels conjunts és un subconjunt estricte d'un atre es denomina clutter, una anticadena de conjunts o un conjunt desordenat. Per eixemple, la família de subconjunts de k elements d'un conjunt de n elements és una família de Sperner. Cap conjunt d'esta família pot contindre a cap dels demés, ya que un conjunt contenidor deu ser estrictament major que el conjunt que conté, i en esta família tots els conjunts tenen el mateix tamany. El valor de k que fa que este eixemple tinga tants conjunts com siga possible és n/2 si n és parell, o qualsevol dels sancers més propencs a n/2 si n és impar. Per a esta elecció, el número de conjunts en la família és $(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })$.

La teorema de Sperner establix que estos eixemples són les famílies de Sperner més grans possibles sobre un conjunt de n elements. Formalment, la teorema establix que,

1. Per a cada família de Sperner S l'unió de la qual tinga un total de n elements, $|S|\le (\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }),$ i
2. L'igualtat es complix si i solament si S consta de tots els subconjunts d'un conjunt de n elements que tenen tamany $\lfloor n/2\rfloor$ o tots els que tenen tamany $\lceil n/2\rceil$.

Órdens parcials

La teorema de Sperner també pot enunciar-se en térmens del teorema de Dilworth. La família de tots els subconjunts d'un conjunt de n elements (el seu conjunt potencia) pot ser parcialment ordenat per inclusió de conjunts. En este orde parcial, es diu que dos elements distints són incomparables quan cap d'ells conté a l'atre. L'esgambi d'un orde parcial és el major número d'elements en una anticadena, un conjunt d'elements incomparables per parells. Traduint esta terminologia al llenguage de conjunts, una anticadena és simplement una família de Sperner, i l'esgambi de l'orde parcial és el número màxim de conjunts en una família de Sperner.

Per lo tant, una atra forma d'enunciar la teorema de Sperner és que l'esgambi de l'orde d'inclusió en un conjunt potencia és $(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })$.

Es diu que un conjunt parcialment ordenat graduat té la propietat de Sperner quan una de les seues anticadenas més grans està formada per un conjunt d'elements que tenen tots el mateix ranc. En esta terminologia, la teorema de Sperner establix que el conjunt parcialment ordenat de tots els subconjunts d'un conjunt finito, parcialment ordenat per inclusió de conjunts, té la propietat de Sperner.

Vore també

• Teorema de Dilworth
• Teorema de Erdös-Ko-Rado

Referències

• .
• .
• .
• .
• Plantilla:Springer.
• .
• .
• .
• X.