La teoria di Sperner

Teorema di Sperner Per il teorema dei simplessi, vedi il lemma di Sperner.

La teoria di Sperner, nella matematica discreta, descrive le famiglie più grandi possibili di insiemi finiti nessuno dei quali contiene altri insiemi nella famiglia. È uno dei risultati centrali nella teoria degli insiemi estremi. Prende il nome da Emanuel Sperner, in chi l'ha pubblicato 1928.

Questo risultato è talvolta chiamato lemma di Sperner, ma il nome "Il tema di Sperner" si riferisce anche a un risultato non correlato sulla colorazione delle triangolazioni. Per differenziare i due risultati, il risultato sulla dimensione di una famiglia Sperner è ora più comunemente noto come teorema di Sperner.

Contenuti 1 Dichiarazione 2 Ordini parziali 3 Prova 4 generalizzazioni 4.1 Niente lunghe catene 4.2 p-composizioni di un insieme 4.3 Nessuna catena lunga nelle composizioni p di un insieme 4.4 Analogo della geometria proiettiva 4.5 Nessuna lunga catena nelle composizioni p di uno spazio proiettivo 5 Guarda anche 6 Riferimenti 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, o un'anticatena di insiemi, o un disordine. Per esempio, la famiglia di sottoinsiemi di k elementi di un insieme di n elementi è una famiglia Sperner. Nessun set in questa famiglia può contenere nessuno degli altri, perché un insieme contenitore deve essere rigorosamente più grande dell'insieme che contiene, e in questa famiglia tutti gli insiemi hanno la stessa dimensione. Il valore di k che fa sì che questo esempio abbia il maggior numero possibile di insiemi è n/2 se n è pari, o uno degli interi più vicini a n/2 se n è dispari. Per questa scelta, il numero di set nella famiglia è {stile di visualizzazione {binomio {n}{lpiano n/2rpiano }}} .

Il teorema di Sperner afferma che questi esempi sono le famiglie Sperner più grandi possibili su un insieme di n elementi. Formalmente, il teorema lo afferma, per ogni famiglia S di Sperner la cui unione ha un totale di n elementi, {stile di visualizzazione |S|leq {alcuni di quelli {n}{lpiano n/2rpiano }},} e l'uguaglianza vale se e solo se S è costituito da tutti i sottoinsiemi di un insieme di n elementi che hanno dimensione {displaystyle lpiano n/2rpiano } o tutti quelli che hanno dimensioni {displaystyle lceil n/2rceil } . Partial orders Sperner's theorem can also be stated in terms of partial order width. La famiglia di tutti i sottoinsiemi di un insieme di n elementi (il suo set di potenza) può essere parzialmente ordinato per inclusione di insiemi; in questo ordine parziale, due elementi distinti si dicono incomparabili quando nessuno dei due contiene l'altro. La larghezza di un ordine parziale è il maggior numero di elementi in un'anticatena, un insieme di elementi incomparabili a coppie. Tradurre questa terminologia nel linguaggio degli insiemi, un'antichain è solo una famiglia Sperner, e la larghezza dell'ordine parziale è il numero massimo di insiemi in una famiglia Sperner. così, un altro modo per affermare il teorema di Sperner è che la larghezza dell'ordine di inclusione su un insieme di potenze lo è {stile di visualizzazione {alcuni di quelli {n}{lpiano n/2rpiano }}} .

Si dice che un insieme parzialmente ordinato graduato abbia la proprietà Sperner quando una delle sue più grandi anticatene è formata da un insieme di elementi che hanno tutti lo stesso rango. In questa terminologia, Il teorema di Sperner afferma che l'insieme parzialmente ordinato di tutti i sottoinsiemi di un insieme finito, parzialmente ordinato per inclusione di insiemi, ha la proprietà Sperner.

Proof There are many proofs of Sperner's theorem, ognuno porta a diverse generalizzazioni (vedi Anderson (1987)).

La seguente prova è dovuta a Lubell (1966). Sia sk il numero di k-insiemi in S. Per tutti 0 ≤ k ≤ n, {stile di visualizzazione {n scegli lpiano {n/2}piano }geq {n scegli k}} e, così, {stile di visualizzazione {S_{K} Sopra {n scegli lpiano {n/2}piano }}leq {S_{K} Sopra {n scegli k}}.} Poiché S è un'anticatena, possiamo sommare la disuguaglianza di cui sopra da k = 0 a n e quindi applicare la disuguaglianza LYM per ottenere {somma dello stile di visualizzazione _{k=0}^{n}{S_{K} Sopra {n scegli lpiano {n/2}piano }}leq somma _{k=0}^{n}{S_{K} Sopra {n scegli k}}leq 1,} che significa {stile di visualizzazione |S|=somma _{k=0}^{n}S_{K}leq {n scegli lpiano {n/2}piano }.} Questo completa la dimostrazione della parte 1.

Per avere uguaglianza, tutte le disuguaglianze nella dimostrazione precedente devono essere uguaglianze. Da {stile di visualizzazione {n scegli lpiano {n/2}piano }={n scegli k}} se e solo se {displaystyle k=lpiano {n/2}piano } o {displaystyle lceil {n/2}rcel ,} concludiamo che l'uguaglianza implica che S consiste solo di insiemi di dimensioni {displaystyle lfloor {n/2}piano } o {displaystyle lceil {n/2}rcel .} Per anche n che conclude la dimostrazione della parte 2.

Per dispari n c'è più lavoro da fare, che omettiamo qui perché è complicato. Vedi Anderson (1987), pp. 3–4.

Generalizations There are several generalizations of Sperner's theorem for subsets of {stile di visualizzazione {matematico {P}}(e),} il poset di tutti i sottoinsiemi di E.

No long chains A chain is a subfamily {stile di visualizzazione {S_{0},S_{1},punti ,S_{r}}sottoseq {matematico {P}}(e)} che è totalmente ordinato, cioè., {stile di visualizzazione S_{0}sottoinsieme S_{1}sottoinsieme punti sottoinsieme S_{r}} (eventualmente dopo la rinumerazione). La catena ha r + 1 membri e lunghezza r. Una famiglia senza catene (chiamato anche famiglia r) è una famiglia di sottoinsiemi di E che non contiene alcuna catena di lunghezza r. foresta (1945) dimostrato che la dimensione massima di una famiglia priva di catena r è la somma dei coefficienti binomiali r maggiori {stile di visualizzazione {alcuni di quelli {n}{io}}} . Il caso r = 1 è la teoria di Sperner.

p-compositions of a set In the set {stile di visualizzazione {matematico {P}}(e)^{p}} di p-tuple di sottoinsiemi di E, diciamo una p-tupla {stile di visualizzazione (S_{1},punti ,S_{p})} è ≤ un altro, {stile di visualizzazione (T_{1},punti ,T_{p}),} Se {stile di visualizzazione S_{io}sottosezione T_{io}} per ogni i = 1,2,...,p. Noi chiamiamo {stile di visualizzazione (S_{1},punti ,S_{p})} una p-composizione di E se gli insiemi {stile di visualizzazione S_{1},punti ,S_{p}} formare una partizione di E. Meshalkin (1963) dimostrato che la dimensione massima di un'anticatena di p-composizioni è il più grande coefficiente p-multinomiale {stile di visualizzazione {alcuni di quelli {n}{n_{1} n_{2} dots n_{p}}},} questo è, il coefficiente in cui tutti ni sono il più quasi uguali possibile (cioè., differiscono al massimo 1). Meshalkin lo ha dimostrato dimostrando una disuguaglianza LYM generalizzata.

Il caso p = 2 è la teoria di Sperner, perché poi {stile di visualizzazione S_{2}=Esetmeno S_{1}} e le ipotesi si riducono agli insiemi {stile di visualizzazione S_{1}} essere una famiglia Sperner.

No long chains in p-compositions of a set Beck & Zaslavsky (2002) ha combinato i teoremi di Erdös e Meshalkin adattando la dimostrazione di Meshalkin della sua disuguaglianza LYM generalizzata. Hanno mostrato che la dimensione più grande di una famiglia di p-composizioni tale che gli insiemi nella i-esima posizione delle p-tuple, ignorando le duplicazioni, sono privi di catena R, per ogni {displaystyle i=1,2,punti ,p-1} (ma non necessariamente per i = p), non è maggiore della somma del {stile di visualizzazione r^{p-1}} coefficienti p-multinomiali maggiori.

Projective geometry analog In the finite projective geometry PG(d, Fq) di dimensione d su un campo finito di ordine q, permettere {stile di visualizzazione {matematico {l}}(p,F_{q})} essere la famiglia di tutti i sottospazi. Quando parzialmente ordinato per inclusione di set, questa famiglia è un reticolo. Rota & Harper (1971) ha dimostrato che la dimensione più grande di un'anticatena in {stile di visualizzazione {matematico {l}}(p,F_{q})} è il più grande coefficiente gaussiano {stile di visualizzazione {inizio{bmatrice}d+1noto{bmatrice}};} questo è l'analogo della geometria proiettiva, o q-analogico, della teoria di Sperner.

Hanno inoltre dimostrato che la dimensione più grande di una famiglia senza catena a R {stile di visualizzazione {matematico {l}}(p,F_{q})} è la somma dei coefficienti gaussiani r maggiori. La loro dimostrazione è da un analogo proiettivo della disuguaglianza LYM.

No long chains in p-compositions of a projective space Beck & Zaslavsky (2003) ha ottenuto una generalizzazione simile a Meshalkin del teorema di Rota-Harper. In PG(d, Fq), una sequenza Meshalkin di lunghezza p è una sequenza {stile di visualizzazione (UN_{1},ldot ,UN_{p})} di sottospazi proiettivi tali che nessun sottospazio proprio di PG(d, Fq) li contiene tutti e le loro dimensioni si sommano {stile di visualizzazione d-p+1} . Il teorema è che una famiglia di sequenze Meshalkin di lunghezza p in PG(d, Fq), tale che i sottospazi che compaiono nella posizione i delle sequenze non contengano catena di lunghezza r per ciascuno {displaystyle i=1,2,punti ,p-1,} non è più della somma del più grande {stile di visualizzazione r^{p-1}} delle quantità {stile di visualizzazione {inizio{bmatrice}d+1n_{1} n_{2} dots n_{p}fine{bmatrice}}q^{S_{2}(n_{1},ldot ,n_{p})},} dove {stile di visualizzazione {inizio{bmatrice}d+1n_{1} n_{2} dots n_{p}fine{bmatrice}}} (in cui lo assumiamo {stile di visualizzazione d+1=n_{1}+cdot +n_{p}} ) denota il coefficiente p-gaussiano {stile di visualizzazione {inizio{bmatrice}d+1n_{1}fine{bmatrice}}{inizio{bmatrice}d+1-n_{1}\n_{2}fine{bmatrice}}cdot {inizio{bmatrice}d+1-(n_{1}+cdot +n_{p-1})\n_{p}fine{bmatrice}}} e {stile di visualizzazione s_{2}(n_{1},ldot ,n_{p}):=n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3}+n_{1}n_{4}+cdot +n_{p-1}n_{p},} la seconda funzione simmetrica elementare dei numeri {stile di visualizzazione n_{1},n_{2},punti ,n_{p}.} See also Mathematics portal Dilworth's theorem References Anderson, Ian (1987), Combinatoria degli insiemi finiti, la stampa dell'università di Oxford. Beck, Mattia; Zaslavskij, Tommaso (2002), "Un più corto, più semplice, prova più forte dei limiti Meshalkin-Hochberg-Hirsch su anticatene a componenti", Rivista di teoria combinatoria, Serie A, 100 (1): 196–199, arXiv:matematica/0112068, doi:10.1006/jcta.2002.3295, SIG 1932078, S2CID 8136773. Beck, Mattia; Zaslavskij, Tommaso (2003), "Un teorema di Meshalkin per geometrie proiettive", Rivista di teoria combinatoria, Serie A, 102 (2): 433–441, arXiv:matematica/0112069, doi:10.1016/S0097-3165(03)00049-9, SIG 1979545, S2CID 992137. Engel, Corrado (1997), Teoria di Sperner, Enciclopedia della matematica e sue applicazioni, vol. 65, Cambridge: Cambridge University Press, p. x+417, doi:10.1017/CBO9780511574719, ISBN 0-521-45206-6, SIG 1429390. Engel, K. (2001) [1994], "Il teorema di Sperner", Enciclopedia della matematica, EMS Press Erdős, P. (1945), "Su un lemma di Littlewood e Offord" (PDF), Bollettino dell'American Mathematical Society, 51 (12): 898–902, doi:10.1090/S0002-9904-1945-08454-7, SIG 0014608 Lubell, D. (1966), "Una breve dimostrazione del lemma di Sperner", Rivista di teoria combinatoria, 1 (2): 299, doi:10.1016/S0021-9800(66)80035-2, SIG 0194348. Meshalkin, LD. (1963), "Generalizzazione del teorema di Sperner sul numero di sottoinsiemi di un insieme finito", Teoria della probabilità e sue applicazioni (in russo), 8 (2): 203–204, doi:10.1137/1108023. Rota, Gian-Carlo; Harper, l. H. (1971), "Teoria della corrispondenza, un introduzione", Progressi nella probabilità e argomenti correlati, vol. 1, New York: Dekker, pp. 169–215, SIG 0282855. Sperner, Emanuele (1928), "Un teorema sui sottoinsiemi di un insieme finito", Giornale di matematica (in tedesco), 27 (1): 544–548, doi:10.1007/BF01171114, hdl:10338.dmlcz/127405, JFM 54.0090.06, S2CID 123451223. Collegamenti esterni Il teorema di Sperner al cut-the-knot Il teorema di Sperner sul wiki polymath1 Categorie: Impostare le famiglie Argomenti fattoriali e binomiali