La théorie de Sperner

Théorème de Sperner Pour le théorème sur les simplexes, voir le lemme de Sperner.

La théorie de Sperner, en mathématiques discrètes, décrit les plus grandes familles possibles d'ensembles finis dont aucun ne contient d'autres ensembles dans la famille. C'est l'un des résultats centraux de la théorie des ensembles extrémaux. Il porte le nom d'Emanuel Sperner, qui l'a publié dans 1928.

Ce résultat est parfois appelé lemme de Sperner, mais le nom "Le thème de Sperner" fait également référence à un résultat sans rapport sur les triangulations de coloration. Pour différencier les deux résultats, le résultat sur la taille d'une famille de Sperner est maintenant plus communément appelé théorème de Sperner.

Contenu 1 Déclaration 2 Commandes partielles 3 Preuve 4 Généralisations 4.1 Pas de longues chaînes 4.2 p-compositions d'un ensemble 4.3 Pas de longues chaînes dans les p-compositions d'un ensemble 4.4 Analogue de géométrie projective 4.5 Pas de longues chaînes dans les p-compositions d'un espace projectif 5 Voir également 6 Références 7 External links Statement A family of sets in which none of the sets is a strict subset of another is called a Sperner family, ou une antichaîne d'ensembles, ou un désordre. Par exemple, la famille de sous-ensembles de k éléments d'un ensemble de n éléments est une famille de Sperner. Aucun ensemble de cette famille ne peut contenir les autres, car un ensemble contenant doit être strictement plus grand que l'ensemble qu'il contient, et dans cette famille tous les ensembles ont la même taille. La valeur de k qui fait que cet exemple a autant d'ensembles que possible est n/2 si n est pair, ou l'un des entiers les plus proches de n/2 si n est impair. Pour ce choix, le nombre d'ensembles dans la famille est {style d'affichage {tbinom {n}{létage n/2rétage }}} .

Le théorème de Sperner stipule que ces exemples sont les plus grandes familles de Sperner possibles sur un ensemble de n éléments. Officiellement, le théorème dit que, pour chaque famille de Sperner S dont l'union a un total de n éléments, {style d'affichage |S|leq {certains d'entre eux {n}{létage n/2rétage }},} et l'égalité est vraie si et seulement si S se compose de tous les sous-ensembles d'un ensemble de n éléments qui ont une taille {displaystyle lfloor n/2rfloor } ou tout ce qui a de la taille {displaystyle lceil n/2rceil } . Partial orders Sperner's theorem can also be stated in terms of partial order width. La famille de tous les sous-ensembles d'un ensemble de n éléments (son jeu de puissance) peut être partiellement commandé par set inclusion; dans cet ordre partiel, deux éléments distincts sont dits incomparables quand aucun d'eux ne contient l'autre. La largeur d'un ordre partiel est le plus grand nombre d'éléments dans une antichaîne, un ensemble d'éléments incomparables par paires. Traduire cette terminologie dans le langage des ensembles, une antichaîne n'est qu'une famille Sperner, et la largeur de l'ordre partiel est le nombre maximum d'ensembles dans une famille Sperner. Ainsi, une autre façon d'énoncer le théorème de Sperner est que la largeur de l'ordre d'inclusion sur un ensemble de puissance est {style d'affichage {certains d'entre eux {n}{létage n/2rétage }}} .

Un ensemble gradué partiellement ordonné est dit avoir la propriété de Sperner lorsque l'une de ses plus grandes antichaînes est formée par un ensemble d'éléments qui ont tous le même rang. Dans cette terminologie, Le théorème de Sperner stipule que l'ensemble partiellement ordonné de tous les sous-ensembles d'un ensemble fini, partiellement commandé par set inclusion, possède la propriété de Sperner.

Proof There are many proofs of Sperner's theorem, chacun conduisant à des généralisations différentes (voir Anderson (1987)).

La preuve suivante est due à Lubell (1966). Soit sk le nombre de k-ensembles dans S. Pour tous 0 ≤ k ≤ n, {style d'affichage {n choisir létage {n/2}rétage }gq {n choisir k}} et, Donc, {style d'affichage {s_{k} plus de {n choisir létage {n/2}rétage }}leq {s_{k} plus de {n choisir k}}.} Puisque S est une antichaîne, nous pouvons additionner l'inégalité ci-dessus à partir de k = 0 à n puis appliquer l'inégalité LYM pour obtenir {somme de style d'affichage _{k=0}^{n}{s_{k} plus de {n choisir létage {n/2}rétage }}leq somme _{k=0}^{n}{s_{k} plus de {n choisir k}}leq 1,} ce qui signifie {style d'affichage |S|=somme _{k=0}^{n}s_{k}leq {n choisir létage {n/2}rétage }.} Ceci termine la preuve de la partie 1.

Avoir l'égalité, toutes les inégalités de la preuve précédente doivent être des égalités. Depuis {style d'affichage {n choisir létage {n/2}rétage }={n choisir k}} si et seulement si {style d'affichage k=lfloor {n/2}rétage } ou {style d'affichage {n/2}rcel ,} nous concluons que l'égalité implique que S se compose uniquement d'ensembles de tailles {style d'affichage lfloor {n/2}rétage } ou {style d'affichage {n/2}rcel .} Pour n pair qui conclut la preuve de la partie 2.

Pour impair n il y a plus de travail à faire, que nous omettons ici car c'est compliqué. Voir Anderson (1987), pp. 3–4.

Generalizations There are several generalizations of Sperner's theorem for subsets of {style d'affichage {mathématique {P}}(E),} le poset de tous les sous-ensembles de E.

No long chains A chain is a subfamily {style d'affichage {S_{0},S_{1},des points ,S_{r}}sous-ensemble {mathématique {P}}(E)} c'est totalement commandé, c'est à dire., {style d'affichage S_{0}sous-ensemble S_{1}sous-ensemble points sous-ensemble S_{r}} (éventuellement après renumérotation). La chaîne a r + 1 membres et longueur r. Une famille sans chaîne R (également appelée famille r) est une famille de sous-ensembles de E qui ne contient aucune chaîne de longueur r. Forêt (1945) prouvé que la plus grande taille d'une famille sans chaîne r est la somme des r plus grands coefficients binomiaux {style d'affichage {certains d'entre eux {n}{je}}} . Le cas r = 1 est la théorie de Sperner.

p-compositions of a set In the set {style d'affichage {mathématique {P}}(E)^{p}} de p-uplets de sous-ensembles de E, on dit un p-uplet {style d'affichage (S_{1},des points ,S_{p})} est ≤ un autre, {style d'affichage (T_{1},des points ,T_{p}),} si {style d'affichage S_{je}sous-ensemble T_{je}} pour chaque i = 1,2,...,p. Nous appelons {style d'affichage (S_{1},des points ,S_{p})} une p-composition de E si les ensembles {style d'affichage S_{1},des points ,S_{p}} forment une partition de E. Meshalkin (1963) prouvé que la taille maximale d'une antichaîne de p-compositions est le plus grand coefficient p-multinomial {style d'affichage {certains d'entre eux {n}{n_{1} n_{2} dots n_{p}}},} C'est, le coefficient dans lequel tous les ni sont aussi proches que possible (c'est à dire., ils diffèrent au plus 1). Meshalkin l'a prouvé en prouvant une inégalité LYM généralisée.

Le cas p = 2 est la théorie de Sperner, parce qu'alors {style d'affichage S_{2}=Esetmoins S_{1}} et les hypothèses se réduisent aux ensembles {style d'affichage S_{1}} être une famille Sperner.

No long chains in p-compositions of a set Beck & Zaslavsky (2002) combiné les théorèmes d'Erdös et de Meshalkin en adaptant la preuve de Meshalkin de son inégalité LYM généralisée. Ils ont montré que la plus grande taille d'une famille de p-compositions telle que les ensembles en i-ième position des p-uplets, ignorer les doublons, sont sans chaîne r, pour chaque {style d'affichage i=1,2,points ,p-1} (mais pas nécessairement pour i = p), n'est pas supérieur à la somme des {style d'affichage r^{p-1}} plus grands coefficients p-multinomiaux.

Projective geometry analog In the finite projective geometry PG(ré, Fq) de dimension d sur un corps fini d'ordre q, laisser {style d'affichage {mathématique {L}}(p,F_{q})} être la famille de tous les sous-espaces. Lorsqu'il est partiellement commandé par set inclusion, cette famille est un treillis. Rota & Harper (1971) a prouvé que la plus grande taille d'une antichaîne dans {style d'affichage {mathématique {L}}(p,F_{q})} est le plus grand coefficient gaussien {style d'affichage {commencer{bmatrice}j+1connu{bmatrice}};} c'est l'analogue de la géométrie projective, ou q-analogique, de la théorie de Sperner.

Ils ont en outre prouvé que la plus grande taille d'une famille sans chaîne r dans {style d'affichage {mathématique {L}}(p,F_{q})} est la somme des r plus grands coefficients gaussiens. Leur preuve est par un analogue projectif de l'inégalité LYM.

No long chains in p-compositions of a projective space Beck & Zaslavsky (2003) obtenu une généralisation de type Meshalkin du théorème de Rota-Harper. Dans PG(ré, Fq), une suite de Meshalkin de longueur p est une suite {style d'affichage (UN_{1},ldots ,UN_{p})} de sous-espaces projectifs tels qu'aucun sous-espace propre de PG(ré, Fq) les contient tous et leurs dimensions totalisent {style d'affichage d-p+1} . Le théorème est qu'une famille de séquences de Meshalkin de longueur p dans PG(ré, Fq), tel que les sous-espaces apparaissant en position i des séquences ne contiennent aucune chaîne de longueur r pour chaque {style d'affichage i=1,2,points ,p-1,} n'est pas supérieur à la somme des plus grands {style d'affichage r^{p-1}} des quantités {style d'affichage {commencer{bmatrice}j+1n_{1} n_{2} dots n_{p}fin{bmatrice}}q ^{s_{2}(n_{1},ldots ,n_{p})},} où {style d'affichage {commencer{bmatrice}j+1n_{1} n_{2} dots n_{p}fin{bmatrice}}} (dans lequel on suppose que {displaystyle d+1=n_{1}+cdots +n_{p}} ) désigne le coefficient p-gaussien {style d'affichage {commencer{bmatrice}j+1n_{1}fin{bmatrice}}{commencer{bmatrice}j+1-n_{1}\n_{2}fin{bmatrice}}cdots {commencer{bmatrice}j+1-(n_{1}+cdots +n_{p-1})\n_{p}fin{bmatrice}}} et {style d'affichage 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},} la deuxième fonction symétrique élémentaire des nombres {displaystyle n_{1},n_{2},des points ,n_{p}.} See also Mathematics portal Dilworth's theorem References Anderson, Ian (1987), Combinatoire des ensembles finis, Presse universitaire d'Oxford. Beck, Mathias; Zaslavski, Thomas (2002), "Un plus court, plus simple, preuve plus forte des bornes de Meshalkin-Hochberg-Hirsch sur les antichaînes par composant", Journal de théorie combinatoire, Série A, 100 (1): 196–199, arXiv:mathématiques/0112068, est ce que je:10.1006/jcta.2002.3295, M 1932078, S2CID 8136773. Beck, Mathias; Zaslavski, Thomas (2003), "Un théorème de Meshalkin pour les géométries projectives", Journal de théorie combinatoire, Série A, 102 (2): 433–441, arXiv:mathématiques/0112069, est ce que je:10.1016/S0097-3165(03)00049-9, M 1979545, S2CID 992137. Engel, Conrad (1997), Théorie de Sperner, Encyclopédie des mathématiques et de ses applications, volume. 65, Cambridge: la presse de l'Universite de Cambridge, p. x+417, est ce que je:10.1017/CBO9780511574719, ISBN 0-521-45206-6, M 1429390. Engel, K. (2001) [1994], "Théorème de Sperner", Encyclopédie des mathématiques, EMS Press Erdős, P. (1945), "Sur un lemme de Littlewood et Offord" (PDF), Bulletin de l'American Mathematical Society, 51 (12): 898–902, est ce que je:10.1090/S0002-9904-1945-08454-7, M 0014608 Lubell, ré. (1966), "Une courte preuve du lemme de Sperner", Journal de théorie combinatoire, 1 (2): 299, est ce que je:10.1016/S0021-9800(66)80035-2, M 0194348. Meshalkin, L.D. (1963), "Généralisation du théorème de Sperner sur le nombre de sous-ensembles d'un ensemble fini", Théorie des probabilités et ses applications (en russe), 8 (2): 203–204, est ce que je:10.1137/1108023. Rotation, Gian-Carlo; harpiste, L. H. (1971), "Théorie de l'appariement, une introduction", Avancées en probabilités et sujets connexes, Volume. 1, New York: Dekker, pp. 169–215, M 0282855. Sperner, Emmanuel (1928), "Un théorème sur les sous-ensembles d'un ensemble fini", Journal mathématique (en allemand), 27 (1): 544–548, est ce que je:10.1007/BF01171114, hdl:10338.dmlcz/127405, JFM 54.0090.06, S2CID 123451223. Liens externes Théorème de Sperner à couper le nœud Théorème de Sperner sur le wiki polymath1 Catégories: Définir les famillesThèmes factoriels et binomiaux