I building set e l'intervallo simplesso-permutaedro

(1)

Universit`

a degli Studi di Pisa

Corso di Laurea Magistrale in Matematica

Tesi di Laurea Magistrale

I building set e l’intervallo

simplesso-permutaedro

CANDIDATO

Andrea Nari

RELATORE

CONTRORELATORE

Prof. Giovanni Gaiffi

Prof. Filippo Callegaro

(2)

(3)

Introduzione

I nestoedri sono una famiglia parzialmente ordinata di politopi n-dimensionali, che inizia dal simplesso e termina con il permutaedro. Vari elementi di questa famiglia hanno rivestito un ruolo importante nella ricerca matematica, anche prima che il termine nestoedro venisse coniato da Postnikov, Reiner e Williams in [26]. Un esempio è fornito dall’associaedro di Stasheff: esso è stato introdotto per la prima volta da Stasheff in [27] come un complesso cellulare, mentre la prima realizzazione come politopo è apparsa in una pubblicazione di Lee in [23]. In seguito è stato realizzato come politopo in molti altri modi da molti autori (fra cui Stasheff e Shnider in [28]). Esistono anche varie definizioni di nestoedri ge-neralizzati, alcuni dei quali verranno presentati nell’ultimo capitolo di questa tesi. I nestoedri vengono introdotti in vari modi: nei lavori di Zelevinski [31], Postnikov, Reiner e Williams [26], Buchstaber [3], Erokhovets [9] e Volodin [30] i nestoedri sono definiti come somma di Minkowski di simplessi, generati da politopi combinatori. Questo approccio viene semplificato dal lavoro di Fenn [12], che elimina i parametri non negativi degli approcci precedenti ed identifica i simplessi della somma di Minkowski con dei nested set.

Un secondo approccio `e quello seguito da A. Postnikov in [25]: i nestoedri sono introdotti come delle generalizzazioni dei permutaedri. Essi sono ottenuti da un permutaedro tramite il trasporto parallelo dei suoi facet.

Un terzo approccio proviene dalla versione reale della teoria dei wonderful models di De Concini-Procesi [7]: Gaiffi ha mostrato come costruire famiglie generalizzate di nestoedri associati ad arrangiamenti di iperpiani, prima sotto forma di variet`a con angoli (vedi [15], [16]) poi come politopi, all’interno della pi`u generale costruzione di permutonestoedri (vedi [17]).

Un ultimo approccio `e quello di E.M.Feichtner e B.Sturmfels: in [11] introdu-cono i nestoedri in collegamento con i Bergman fan e la geometria tropicale.

In tutte le costruzioni emergono due particolari strutture combinatorie, i building set e i nested set. Una prima definizione di nested set compare nel lavoro di Fulton e MacPherson sulla compattificazione di spazi di configurazioni ([14]); successivamente De Concini e Procesi [7] hanno introdotto il concetto di building set, generalizzando nel contempo i nested set. Feichtner e Kozlov in [10] li hanno poi definiti in un modo puramente combinatorio.

(4)

Dato un building set B, il nestoedro corrispondente è definito come il politopo semplice il cui reticolo delle facce sia isomorfo al complesso dei nested set di B. Essi possono essere ottenuti a partire dai simplessi, troncandone le facce con degli iperpiani. Questo è l’approccio seguito in Petrić [24] e Doˇsen e Petrić [8]. In questa tesi, ripercorrendo il lavoro di Petrić in [24], descriveremo i nestoedri attraverso lo studio delle loro facce. Per fare ciò applicheremo iterativamente la tecnica di Feichtner-Kozlov [10] per la formazione dei complessi simpliciali di nested set. Questi complessi permettono di mettere in relazione gli α-building set dell’insieme {1, . . . , n + 1} con i nestoedri n-dimensionali: questa relazione induce un ordinamento parziale sull’insieme dei nestoedri, l’intervallo simplesso-permutaedro. Inoltre, sempre seguendo Petric [24], introdurremo i building set piatti ed i corrispondenti complessi piatti. In tal modo potremo estendere la relazione precedente a tutti i politopi semplici n-dimensionali: mostreremo che esiste un isomorfismo tra i complessi piatti ed i blowup combinatori (introdotti da Feichtner e Kozlov in [10]).

Nello specifico, questa tesi `e cos`ı strutturata:

Nel capitolo 1 introdurremo le relazioni d’ordine, i poset ed i reticoli. Nei reticoli sono definiti due operatori: il meet ed il join. Tramite questi operatori ne si determina la struttura, il minimo ed il massimo. Questa struttura pu`o essere rappresentata graficamente attraverso il diagramma di Hasse.

Nel capitolo 2 definiremo i politopi e mostreremo come costruirli attraverso l’inviluppo convesso di un insieme finito di punti. Definiremo i coni e mostreremo che esiste una corrispondenza tra le facce dei coni e quelle dei politopi. Definire-mo i politopi semplici e ne Definire-mostrereDefinire-mo tre esempi: il simplesso, l’associaedro ed il permutaedro. Definiremo poi una tecnica per creare nuovi politopi: il troncamento di una faccia. In particolare i nestoedri sono tutti ottenuti at-traverso troncamenti successivi dei simplessi. Infine definiremo una relazione di equivalenza tra i politopi: l’equivalenza combinatoria. In questa tesi stu-dieremo ed identificheremo i politopi sempre a meno di equivalenza combinatoria. Nel capitolo 3 introdurremo gli ipergrafi, i building set (ed un loro sottoinsie-me, gli α-buliding set) ed i nested set. Per ogni α-building set definiremo le sue costruzioni ed i suoi costrutti: questi formano un poset, detto politopo astratto. Proveremo che per ogni α-building set esiste un unico politopo semplice, il cui reticolo delle facce `e isomorfo al suo politopo astratto. Questi politopi sono i nestoedri: essi formano un reticolo, l’intervallo simplesso-permutaedro.

Nel capitolo 4 introdurremo le somme formali e, tramite la teoria di Feichtner-Kozlov [10], le useremo per iterare i complessi di nested set. L’ostacolo di questo procedimento `e che ad ogni iterazione aumentano esponenzialmente le coppie di parentesi graffe, rendendo quasi impossibile scriverne il risultato. Come fatto da Petri´c in [24], mostreremo come presentare gli elementi di un nested set tramite gli elementi di un semigruppo commutativo liberamente generato. Vogliamo iterare il procedimento per generare nuovi complessi di nested set: in questo modo creeremo i building set piatti ed i loro rispettivi complessi piatti. Proveremo che esiste un isomorfismo tra i complessi di nested set, i

(5)

com-plessi piatti ed i blowup combinatori, definiti da Feichtner e Kozlov sempre in [10]. Nel capitolo 5 mostreremo come ottenere il nestoedro corrispondente ad un determinato building set, come fatto da Doˇsen e Petrić in [8]. Studieremo l’intervallo simplesso-permutaedro nel caso bidimensionale e tridimensionale, evidenziando la presenza di politopi interessanti ed i loro building set corrispon-denti: scopriremo che nell’intervallo simplesso-permutaedro possiamo trovare altri politopi molto famosi, come il quadrato, il pentagono, la piramide a base quadrata, il cubo e l’associaedro. Infine utilizzeremo i blowup combinatori ed i complessi piatti per determinare il reticolo delle facce dei nestoedri generalizzati. Perciò scopriremo che per studiare molti politopi semplici (a meno di equi-valenza combinatoria) è sufficiente analizzarne il corrispondente complesso. La struttura di un politopo semplice può essere determinata attraverso un’anali-si combinatoria: questo ne facilita di molto la sua comprenun’anali-sione, specie per dimensioni grandi.

(6)

(7)

Indice

Introduzione i 1 I poset ed i reticoli 1 1.1 I poset . . . 1 1.2 I semireticoli superiori . . . 3 1.3 I semireticoli inferiori . . . 4 1.4 I reticoli . . . 5 1.5 Il diagramma di Hasse . . . 6 2 I politopi 7 2.1 Gli insiemi convessi . . . 7

2.2 I politopi convessi . . . 8 2.3 Il simplesso . . . 10 2.4 Il permutaedro . . . 11 2.5 L’associaedro . . . 12 2.6 I coni . . . 13 2.7 Le facce di un cono . . . 14 2.8 I fan . . . 15 2.9 Il troncamento di un politopo . . . 16 3 L’intervallo simplesso-permutaedro 17 3.1 Gli ipergrafi . . . 17 3.2 I complessi simpliciali . . . 19 3.3 I building set . . . 19 3.4 I nested set . . . 22 3.5 Le costruzioni . . . 23

3.6 Gli ipergrafi affini . . . 25

3.7 I costrutti . . . 27

3.8 L’intervallo simplesso-permutaedro . . . 29

4 Il complesso dei nested set 31 4.1 Le somme formali . . . 31

4.2 Iterando i complessi di nested set . . . 32

4.3 La realizzazione fedele dei complessi . . . 34

4.4 I building set piatti . . . 37

(8)

5 I nestoedri 41

5.1 La realizzazione geometrica . . . 41

5.2 I vertici . . . 42

5.3 Il reticolo delle facce . . . 44

5.4 Il caso bidimensionale . . . 45

5.5 Il caso tridimensionale . . . 46

5.6 Un’estensione dei nestoedri . . . 48

A Tavole grafiche 51 A.1 Il diagramma di un reticolo delle facce . . . 51

A.2 Le basi di un complesso piatto . . . 52

(9)

Capitolo 1

I poset ed i reticoli

In questo primo capitolo introdurremo i poset ed i reticoli, riprendendo le notazioni usate in [13]. La teoria dei poset e dei reticoli `e necessaria per poter studiare l’intervallo simplesso permutaedro, che `e un reticolo (e quindi un poset).

1.1 I poset

Definizione 1.1. Un poset (X, ≤) è un insieme X dotato di una relazione ≤ riflessiva, antisimmetrica e transitiva, detta ordinamento parziale o relazione d’ordine di X. Se (X, ≤) è un poset, diremo che l’insieme X è ordinato da ≤. Esempio 1.1. Sia P = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}, allora possiamo dotare P della struttura di poset definendo ∀p, q ∈ P la relazione p ≤ q ⇔ p|q.

Definizione 1.2. Se (X, ≤) è un poset, due elementi a, b ∈ X si dicono con-frontabili se a ≤ b o b ≤ a. Un insieme X è totalmente ordinato da ≤ se (X, ≤) è un poset ed ogni coppia di elementi di X è confrontabile.

Esempio 1.2. Preso (P, ≤) come sopra, 12 e 4 sono confrontabili perché 4|12 ⇒ 4 ≤ 12. Invece 12 e 5 non lo sono, perciò P non è totalmente ordinato da ≤. Definizione 1.3. Dato un poset (X, ≤), la relazione opposta a ≤ è la relazione d’ordine ≥ su X cos`ı definita: ∀a, b ∈ X, a ≥ b ⇔ b ≤ a.

Notazione 1.1. Dato un poset (X, ≤) e due elementi x, y ∈ X, diremo che x < y ⇔ x ≤ y e x 6= y. Dualmente, diremo che x > y ⇔ x ≥ y e x 6= y. Esempio 1.3. Preso (P, ≤) come sopra, ∀p, q ∈ P , p ≥ q ⇔ q ≤ p, ossia p ≥ q ⇔ q|p. Perci`o 12 ≥ 4 ⇒ 12 > 4 e 4 < 12.

Osservazione 1.1. Dato un poset (X, ≤), < e > non sono relazioni d’ordine di X perch´e non sono riflessive.

Definizione 1.4. Dato un poset (X, ≤), il suo poset opposto `e (X, ≤)op_{, un}

poset dove l’insieme X `e ordinato dall’ordinamento opposto ≥ dell’ordinamento parziale ≤ del poset (X, ≤).

Esempio 1.4. Nel caso dell’Esempio 1.1, (P, ≤)op `e un poset dove ∀p, q ∈ P , p ≤ q ⇔ q|p, ossia se q ≤ p in (P, ≤). Perci`o 12 ≤ 4 in (P, ≤)op.

(10)

Definizione 1.5. Dato un poset (X, ≤) e ∅ 6= A ⊆ X, un elemento x ∈ X `e un maggiorante di A se ∀y ∈ A, y ≤ x. Dualmente, z ∈ X `e un minorante di A se ∀y ∈ A, z ≤ y. Indicheremo con m(A) l’insieme dei minoranti di A e con M (A) il suo insieme dei maggioranti.

Definizione 1.6. Siano (X, ≤) un poset ed A ⊆ X. Un elemento b ∈ A si dice minimo di A se ∀a ∈ A, b ≤ a. Analogamente un elemento c ∈ A si dice massimo di A se ∀a ∈ A, a ≤ c.

Lemma 1.1. Sia (X, ≤) un poset. Allora ∀A ⊆ X il massimo e il minimo di A, se esistono, sono unici.

Dimostrazione. Supponiamo per assurdo che ci siano due massimi m, m0 ∈ A. Per definizione di massimo si ha che m0≤ m e m ≤ m0_{, ma ≤ `}_{e antisimmetrica:}

perciò m0= m = max A. La verifica è analoga per l’unicità del minimo. Esempio 1.5. Sia (P, ≤) il poset dell’Esempio 1.1 e sia Q = {2, 4, 6, 12} ⊆ P . Allora m(Q) = {1, 2} e M (Q) = {12, 60}: perciò 1 è un minorante di Q, 60 è un suo maggiorante, 2 è il minimo di Q e 12 il suo massimo.

Notazione 1.2. Indicheremo con max A il massimo di A e con min A il minimo. Definizione 1.7. Sia (X, ≤) un poset. ∀A ⊆ X, un elemento s ∈ X `e detto estremo superiore di A se `e il minimo dei maggioranti di A, ossia se:

1. s ∈ M (A)

2. Se b ∈ X e a ≤ b ∀a ∈ A, allora s ≤ b

Definizione 1.8. Dualmente, un elemento t ∈ X `e detto estremo inferiore di A se `e il massimo dei minoranti di A, ossia se:

1. t ∈ m(A)

2. Se c ∈ X e c ≤ a ∀a ∈ A, allora c ≤ t

Notazione 1.3. Indicheremo con sup A o ∨A l’estremo superiore di A e con inf A o ∧A il suo estremo inferiore.

Esempio 1.6. Sia (P, ≤) come nell’Esempio 1.1 e sia R={3, 4, 6}. Allora 1 `e l’estremo inferiore di R, mentre 12 `e il suo estremo superiore.

Osservazione 1.2. Se (X, ≤) `e un poset, l’insieme dei maggioranti di ∅ ⊆ X `

e M (∅) = X; pertanto sup ∅ esiste ⇔ esiste min X e risulta sup ∅ = min X. Analogamente m(∅) = X, quindi inf ∅ esiste ⇔ esiste max X e inf ∅ = max X. Notazione 1.4. Indicheremo max X con > o X> e min X con ⊥ o X⊥.

Esempio 1.7. P ha 1 come minimo e 60 come massimo, quindi 1 = P⊥ e 60 = P>.

Definizione 1.9. Una bandiera B di un poset (X, ≤) `e un insieme massimale B = {x0, x1. . . , xn, xn+1} ⊆ X tale che xi < xi+1 ∀i ∈ {0, . . . , n}. Un poset

con minimo e massimo ha rango n se ogni sua bandiera ha cardinalit`a n + 2. Osservazione 1.3. Se ∃ ⊥ e >, ∀B bandiera di X si ha x0=⊥ e xn+1= >.

(11)

1.2 I semireticoli superiori

Definizione 1.10. Un poset (X, ≤) non vuoto si dice semireticolo superiore o ∨-semireticolo se ∀F ⊆ X tale che F `e finito, esiste il sup F .

Osservazione 1.4. Se (X, ≤) è un semireticolo superiore, allora X ha l’elemento minimo perché ∅ è un insieme finito e min X = sup ∅.

Proposizione 1.1. Un poset (X, ≤) `e un semireticolo superiore se e solo se 1. X ha minimo

2. Per ogni a, b ∈ X, esiste sup{a, b}.

Dimostrazione. L’implicazione destra è ovvia: proviamo l’altra implicazione. Il sup è associativo, perché l’esistenza del sup tra due elementi implica l’esistenza del sup di un insieme F 6= ∅ con un numero finito di elementi. Infatti, dati tre elementi a, b, c ∈ X, si ha che

sup{sup{a, b}, c} = sup{a, b, c} = sup{a, sup{b, c}} Se X ha il minimo, allora min X = sup ∅, per cui abbiamo la tesi.

La caratterizzazione precedente permette di definire un’operazione tra gli elementi di un semireticolo superiore:

Definizione 1.11. Dato un semireticolo superiore (X, ≤), l’operatore unione o join ∨ : X × X → X associa ad ogni coppia di elementi a, b ∈ X l’elemento

∨(a, b) = a ∨ b = sup{a, b}

Esempio 1.9. Il poset (P, ≤) dell’Esempio 1.1 `e un semireticolo superiore perch´e ha 1 come minimo e ∀p, q ∈ P , ∨(p, q) = p ∨ q = mcm(p, q) ∈ P .

Lemma 1.2. L’operatore unione soddisfa le seguenti propriet`a: 1. ∨ `e associativo,

2. ∨ `e commutativo, 3. ∨ `e idempotente,

4. ∨ ha come elemento neutro ⊥.

Definizione 1.12. Un insieme (M, ?, e) si dice monoide se ? : M × M → M `e un’operazione associativa con elemento neutro e.

Proposizione 1.2. Se (X, ≤) è un ∨-semireticolo, allora la terna (X, ∨, ⊥) è un monoide commutativo. Viceversa, se (X, ∨, ⊥) è un monoide commutativo in cui ogni elemento è idempotente, allora esiste un’unica relazione d’ordine ≤ su X tale che (X, ≤) è un ∨-semireticolo, dove ∨ è l’unione di X.

Dimostrazione. L’implicazione destra deriva dal lemma precedente. Per l’altra implicazione definiamo la relazione d’ordine x ≤ y ⇔ x ∨ y = y ∀x, y ∈ X: allora (X, ≤) `e un semireticolo superiore (questa verifica si pu`o trovare in [13]). Sia

un’altra relazione d’ordine su X che induce l’unione ∨. Allora si ha che: ∀x, y ∈ X, x ≤ y ⇔ y = sup{x, y} = x ∨ y ⇔ x y ⇒ ≡ ≤

(12)

1.3 I semireticoli inferiori

Definizione 1.13. Un poset (X, ≤) non vuoto si dice semireticolo inferiore o ∧-semireticolo se ∀F ⊆ X tale che F `e finito, esiste inf F .

Osservazione 1.5. Se (X, ≤) è un semireticolo inferiore, allora X ha l’elemento massimo perché ∅ è un insieme finito e max X = inf ∅.

Cos`ı come visto per il sup, anche l’esistenza dell’inf fra due elementi implica l’esistenza dell’inf di un insieme con un numero finito di elementi. Da ci`o discende la seguente caratterizzazione dei semireticoli inferiori:

Proposizione 1.3. Un poset (X, ≤) `e un semireticolo inferiore se e solo se 1. X ha massimo.

2. Per ogni a, b ∈ X, esiste inf{a, b}.

Anche in questo caso si ha la possibilit`a di definire un’operazione interna al semireticolo inferiore:

Definizione 1.14. Dato un semireticolo inferiore (X, ≤), l’operatore meet o intersezione ∧ : X × X → X associa ad ogni coppia di elementi a, b ∈ X

∧(a, b) = a ∧ b = inf{a, b}

Esempio 1.10. Il poset (P, ≤) dell’Esempio 1.1 `e un semireticolo inferiore perch´e ha 60 come massimo e ∀p, q ∈ P , ∧(p, q) = p ∧ q = M CD(p, q) ∈ P .

Lemma 1.3. Dualmente, l’operatore intersezione soddisfa le seguenti propriet`a: 1. ∧ `e associativo,

2. ∧ `e commutativo, 3. ∧ `e idempotente,

4. ∧ ha come elemento neutro >.

Dalle proprietà di ∧, analogamente al caso superiore, si può provare che: Corollario 1.4. Se (X, ≤) è un semireticolo inferiore, allora la terna (X, ∧, >) `

e un monoide commutativo. Viceversa, se (X, ∧, >) `e un monoide commutativo in cui ogni elemento `e idempotente, allora

a ≤ b ⇔ a ∧ b = a ∀a, b ∈ X `

e l’unica relazione d’ordine su X tale che (X, ≤) `e un semireticolo superiore avente ∧ per intersezione.

Osservazione 1.6. Se (X, ≤) `e un semireticolo inferiore, allora X con la relazione d’ordine opposta ≥ `e un semireticolo superiore (X, ≥). Analogamente, se (X, ≤) `

e un semireticolo superiore, allora (X, ≤)op`e un semireticolo inferiore. Pertanto, possiamo affermare che ogni semireticolo inferiore individua univocamente un semireticolo superiore e viceversa.

(13)

Inoltre osserviamo che dal punto di vista algebrico non vi è alcuna distinzione fra semireticoli inferiori e superiori: entrambi infatti sono monoidi commutativi in cui ogni elemento è idempotente. Tuttavia un semireticolo superiore non sempre può essere considerato simultaneamente anche come semireticolo inferiore.

Infatti la relazione d’ordine ≤ indotta secondo la Proposizione 1.2 e l’ordina-mento parziale indotto secondo il Corollario 1.4 in generale non coincidono: Esempio 1.11. X = {alf abeto} = VS C, con V = {vocali} e C = {consonanti}. Siano c1, c2 ∈ C, v1, v2 ∈ V due coppie di lettere diverse ordinate in ordine

alfabetico. Definiamo gli operatori commutativi ∨ e ∧ tali che ∀c1, c2, v1, v2∈ X:

• vi∧ vi= vi∨ vi= vi e ci∧ ci = ci∨ ci= ci (idempotenza)

• vi∨ ci = ci e vi∧ ci= vi (∨ privilegia le consonanti, ∧ le vocali)

• v1∨ v2= v2 e c1∧ c2= c1(questa scelta serve per arrivare all’assurdo)

• c1∨ c2= z e v1∧ v2= a (l’elemento neutro di ∨ `e a, quello di ∧ `e z)

Si tratta di due leggi di composizione che danno entrambe una struttura di semi-reticolo su X. Però, le due relazioni d’ordine ≤ e , definite nella Proposizione 1.2 e nel Corollario 1.4, sono diverse. Infatti e ≤ i (poiché e ∨ i = i), ma e 6 i (poiché e ∧ i = a). Inoltre r 6≤ s (poiché r ∨ s = z), ma r s (poiché r ∧ s = r).

1.4 I reticoli

Definizione 1.15. Un poset (X, ≤), con |X| ≥ 2, `e un reticolo se ∀F ⊆ X, F finito, esistono sup F e inf F in X.

Esempio 1.12. Un insieme costituito da due soli elementi {⊥, >} con la relazione d’ordine ⊥≤ > è il reticolo banale. Esso è indicato con (2, ≤) = ({⊥, >}, ≤). Osservazione 1.7. Un reticolo (X, ≤) è un ∧-semireticolo ed un ∨-semireticolo,

perci`o possiamo definire su X l’unione e l’intersezione. Inoltre X ha minimo ⊥= sup ∅ e massimo > = inf ∅, e, poich´e |X| ≥ 2, si ha che ⊥6= >.

Esempio 1.13. Il poset (P, ≤) dell’Esempio 1.1 è un reticolo perché |P | ≥ 2 ed è un ∨ e ∧-semireticolo.

Proposizione 1.5. Un reticolo `e una struttura algebrica (X, ∨, ∧, ⊥, >) con: A1 ∨ e ∧ due operazioni commutative, associative e idempotenti.

A2 ⊥ l’elemento neutro di ∨, > l’elemento neutro di ∧ e ⊥6= >. A3 ∀a, b ∈ X, a ∨ (a ∧ b) = a.

A4 ∀a, b ∈ X, a ∧ (a ∨ b) = a.

A3 e A4 sono dette le leggi di assorbimento del reticolo X.

Dimostrazione. Le uniche propriet`a del reticolo che non derivano dai semireticoli sono le leggi di assorbimento. ∀a, b ∈ X a ∧ b ≤ a perci`o, usando la definizione di ∧, si ha che a ∨ (a ∧ b) = a. Analogamente a ≤ a ∨ b, quindi a ∧ (a ∨ b) = a. Osservazione 1.8. Nell’esempio 1.9 dell’alfabeto per avere l’assurdo non devono valere le leggi di assorbimento. Infatti si ha che e ∧ (e ∨ i) = a e c ∨ (c ∧ b) = z.

(14)

Teorema 1.6. Sia (X, ∨, ∧) una struttura algebrica. (X, ∨, ∧) verifica le due leggi di assorbimento ⇔ le due relazioni d’ordine a ≤ b ⇔ a ∨ b = b e a b ⇔ a ∧ b = a ∀a, b ∈ X sono riflessive e vale l’unguaglianza ≤ = .

Dimostrazione. Supponiamo che (X, ∨, ∧) soddisfi le leggi d’assorbimento. Siano a, b ∈ X tali che a ≤ b; allora a ∨ b = b e quindi a ∧ (a ∨ b) = a ∧ b. Per A4 segue che a = a ∧ b ovvero a b. Viceversa siano a, b ∈ X tali che a b, allora a ∧ b = a e quindi (a ∧ b) ∨ b = a ∨ b. Per A3 segue che b = a ∨ b ovvero che a ≤ b. Ma da A3 e A4 segue che ∀a ∈ X si ha che a ∨ a = a ∨ (a ∧ (a ∨ a)) = a, quindi a ≤ a. Analogamente a ∧ a = a ∧ (a ∨ (a ∧ a)) = a, quindi a a.

Viceversa supponiamo che l’ordinamento ≤ = sia riflessivo. Allora ∀a, b ∈ X si ha che a ∧ (a ∧ b) = a ∧ b ⇒ a ∧ b a, quindi a ∧ b ≤ a ⇒ a ∨ (a ∧ b) = a. Analogamente a∨(a∨b) = a∨b ⇒ a∨b ≤ a da cui a a∨b ⇒ a∧(a∨b) = a. Corollario 1.7. Su una struttura algebrica (X, ∨, ∧, ⊥, >) che soddisfi le pro-prietà A1, A2, A3 e A4 si può definire una relazione d’ordine ≤ indotta equivalentemente da ∨ o da ∧. Inoltre l’insieme (X, ≤) è un reticolo.

Notazione 1.5. Poniamo |∅| = −1 e P(X) l’insieme delle parti di X.

Esempio 1.14. Se X 6= ∅ è un insieme finito, (P(X), ⊇) è il reticolo dell’insie-me delle parti di X. perché A ∨ B = A ∩ B e A ∧ B = A ∪ B, > = ∅ e ⊥= X soddisfano A1, A2, A3 e A4. Se |X| = m > 0, allora il reticolo (P(X), ⊇) ha rango m − 1 perché ∀P bandiera di (P(X), ⊇) si ha che |xi| − |xi−1| = 1 per

massimalit`a, quindi |xi| = i ∀i e ogni bandiera ha |X| + 1 elementi.

Notazione 1.6. Dato un (semi)reticolo finito (L, ≤), indicheremo con (L−, ≤) il

poset (L r {L⊥}, ≤) e con (L−, ≤) il poset (L r {L>}, ≤).

1.5 Il diagramma di Hasse

Definizione 1.16. Dato un poset (X, ≤), due suoi elementi x e y sono con-secutivi se x < y (o y < x) e 6 ∃z ∈ X tale che x < z < y (o y < z < x). Il diagramma di Hasse di un poset (X, ≤) `e un grafo i cui vertici corrispondono agli elementi di X nel quale si traccia un arco tra x e y ⇔ x e y sono consecutivi.

Figura 1.1: Il diagramma di Hasse del reticolo (P, ≤) dell’Esempio 1.1 Il diagramma di Hasse di un poset (X, ≤) permette di apprezzarne intuiti-vamente la struttura interna. Nel caso in cui (X, ≤) sia un (semi)reticolo, se collochiamo il minimo ed il massimo di X agli estremi del grafo (come fatto in figura), allora le operazioni ∧ e ∨ hanno un corrispettivo grafico: ∀x, y ∈ X, x ∧ y e x ∨ y sono il primo antenato ed il primo discendente comune di x e y. Esempio 1.15. Preso (P, ≤) come sopra, allora 3 ∧ 10 = 1 e 3 ∨ 10 = 30.

(15)

Capitolo 2

I politopi

In questo secondo capitolo definiremo i politopi (usando le notazioni contenute in [19]) ed i coni (seguendo [2]). Definiremo inoltre tre particolari politopi: il simplesso, il permutaedro e l’associaedro. Questi politopi sono gli elementi pi`u importanti dell’intervallo simplesso-permutaedro.

2.1 Gli insiemi convessi

Definizione 2.1. Sia (Rn_{, h, i) uno spazio vettoriale reale dotato del prodotto}

scalare euclideo h, i. Un insieme S ⊆ Rn _`_{e convesso se ∀x, y ∈ S il segmento}

xy = {λx + (1 − λ)y | 0 ≤ λ ≤ 1} `e interamente contenuto in S.

Osservazione 2.1. L’intersezione di due insiemi convessi `e un insieme convesso. Definizione 2.2. Un insieme T ⊆ Rn_`_{e concavo se non `}_{e convesso. L’inviluppo}

convesso di T `e il pi`_{u piccolo insieme convesso conv(T ) ⊆ R}n _{che contiene T .}

Notazione 2.1. Per convenzione si pone conv(∅) = ∅.

Esempio 2.1. La stella S non è convessa, perché il segmento tra x e y non è contenuto in S. Pertanto S è concava: il suo inviluppo convesso è il pentagono P , che ha per vertici le punte della stella {a, b, c, d, e}.

Figura 2.1: La stella S ed il suo inviluppo convesso P .

Lemma 2.1. Sia S ⊆ Rn un insieme convesso. Allora conv(S) = S ⊆ Span(S) e ∀T ⊆ Rn si ha che conv(S ∪ T ) = conv(S) = S ⇔ T ⊆ S.

(16)

2.2 I politopi convessi

Definizione 2.3. Un politopo convesso P ⊆ Rn _`_{e l’inviluppo convesso di un}

insieme finito di punti (minimali per inviluppo) vert(P ), detti i vertici di P . Sia Af f (P ) ⊆ Rn _{il pi`}_{u piccolo sottospazio affine contenente P : un politopo}

convesso è d-dimensionale se la dimensione affine di Af f (P ) è uguale a d. Notazione 2.2. Con la parola politopo indicheremo i politopi convessi. I politopi 2-dimensionali sono detti poligoni, quelli 3-dimensionali sono detti poliedri. Esempio 2.2. L’insieme P = conv({a, b, c, d, e}) dell’Esempio 2.1 è un poligono. Notazione 2.3. Indicheremo con la parola dimensione e con il simbolo dim anche la dimensione affine e poniamo dim(T ) = dim(Af f (T )) ∀T ⊆ Rn_.

Osservazione 2.2. Sia P un politopo con vert(P ) = {x1, . . . , xn+1}. La giacitura

di Af f (P ) `e uguale a Span({xi− xi+1|1 ≤ i ≤ n}), perci`o ∀ P politopo si ha che

dim(P ) = dim Af f (P ) = dim Span({xi− xi+1|1 ≤ i ≤ n}) ≤ n = |vert(P )| − 1.

Notazione 2.4. Dato un iperpiano H = {x ∈ Rn|ha, xi + b = 0, a, b ∈ Rn

} di Rn_,

indichiamo con H+_{= {x ∈ R}n|ha, xi + b ≥ 0} e H−

= {x ∈ Rn|ha, xi + b ≤ 0}. Definizione 2.4. Dato un iperpiano H ed un politopo P di Rn_{, diremo che H}

supporta P se H ∩ P 6= ∅ e P ⊆ H+_{(o P ⊆ H}−_{), dove il semispazio chiuso H}+

supporta P . L’insieme H ∩ P è detto faccia propria di P . Una faccia di un politopo P è un insieme X per cui X = P , X = ∅ o X è una faccia propria di P . Esempio 2.3. Nel caso dell’Esempio 2.1, la retta r passante per i punti {a, e} supporta il pentagono P . Il segmento ae = r ∩ P è una faccia del politopo P . Notazione 2.5. Indicheremo con F (P ) l’insieme delle facce di un politopo P . Esempio 2.4. Nel caso dell’Esempio 2.1,F (P ) = {∅, ab, bc, cd, de, ea, P }. Lemma 2.2. Un politopo P è uguale all’intersezione di Af f (P ) con tutti i semispazi che lo supportano: la sua frontiera è uguale all’unione delle sue facce. Grazie a questo lemma possiamo definire i politopi in un modo equivalente: Definizione 2.5. Dati H1, . . . , Hn degli iperpiani di Rn, un politopo P ⊆ Rn è

un insieme limitato ottenuto come intersezione finita di semispazi chiusi H_i+:

P = n \ i=1 H_i+= n \ i=1 {x ∈ Rn_{|hx, a} ii + bi ≥ 0} ⊆ Rn

Proposizione 2.2. Sia P un politopo d-dimensionale. Pertanto si ha che: 1. Le facce proprie di P sono dei politopi, perci`o hanno una dimensione. 2. P ha facce j-dimensionali ∀j ∈ {−1, 0, 1, . . . , d − 1}, dette j-facce di P . 3. Ogni faccia di una faccia di P `e una faccia di P .

4. Se P1, P2 sono due facce di P , allora P1∩ P2 `e una faccia di P .

5. Se P1, P2 sono due facce di P e FP∗1,P2 = {F ∈ F (P )|F ⊇ (P1∪ P2)},

P1∗ P2=TFP∗1,P2 =T{F ∈F

∗

(17)

Notazione 2.6. Una faccia F di dim(F ) = f `e un vertice se f = 0, spigolo se f = 1, faccia se f = 2, faccia f-dimensionale se f > 2 e facet se f = d − 1. La faccia ∅ ha dimensione −1 per convenzione.

Teorema 2.3. Le facce di un politopo d-dimensionale P formano il reticolo delle facce di P , il reticolo (F (P ), ⊇) di rango d: F (P )⊥= P eF (P )>= ∅.

Inoltre ∀P1, P2∈F (P ) si ha P1∧ P2= P1∩ P2 e P1∨ P2= P1∗ P2.

Dimostrazione. L’insieme (F (P ), ⊇) è un poset, perché ⊇ è un ordinamento parziale. Inoltre (F (P ), ⊇) ammette massimo e minimo, perché ∀F ∈ F (P ), P ⊇ F ⊇ ∅. Proviamo che (F (P ), ⊇) è un reticolo: per la Proposizione 1.5 basta provare che per ∨ e ∧ (definiti nella Proposizione 2.2 ) valgono le leggi di assorbimento (⊇ è l’ordinamento indotto da ∧ per il Corollario 1.4 ). La prima legge A3 è soddisfatta per il Lemma 2.1, mentre la seconda legge A4 è soddisfatta per la definizione di intersezione finita. Il reticolo ha rango d perché ∀Fn∈F (P ) di dimensione n ∃Fn−1∈F(F ) ⊆ F (P ) di dimensione n−1, perciò

ogni bandiera di (F (P ), ⊇) `e della forma {P = Fd, Fd−1, . . . , F0, F−1= ∅}.

Esempio 2.5. Il diagramma di Hasse del reticolo delle facce di una piramide a base quadrata K `e contenuto nell’Appendice A1.

Definizione 2.6. Due poset (A, ≤) e (B, ) sono isomorfi se esiste un iso-morfismo φ : A → B che conserva la struttura di poset: ∀a1, a2 ∈ A tale che

a1 ≤ a2, φ(a1) φ(a2). Due (semi)reticoli (C, ≤) e (D, ) sono isomorfi se

sono isomorfi come poset e la mappa φ conserva la struttura di (semi)reticoli, ossia φ(c1) ∧ φ(c2) = φ(c1∧ c2) e φ(c1) ∨ φ(c2) = φ(c1∨ c2) ∀c1, c2∈ C.

Definizione 2.7. Due politopi P e Q si dicono combinatoriamente equiva-lenti se (F (P ), ⊇) ∼= (F (Q), ⊇) e si indicano con la notazione P ≈ Q.

Esempio 2.6. Un quadrato ed un trapezio sono combinatoriamente equivalenti perch´e il loro reticolo delle facce `e isomorfo, come mostrato in figura:

Figura 2.2: Due politopi combinatoriamente equivalenti

Definizione 2.8. Un politopo d-dimendionale si dice semplice se ogni vertice `e adiacente ad esattamente d spigoli (o equivalentemente a d facet).

Esempio 2.7. Un quadrato è un politopo semplice, infatti ogni suo vertice è adiacente ad esattamente 2 spigoli. Invece un icosaedro non è un politopo 3-dimensionale semplice, perché ogni suo vertice è adiacente a 5 spigoli.

(18)

2.3 Il simplesso

D’ora in poi, quando parleremo di politopi convessi, lo faremo sempre a meno di equivalenza combinatoria. Il rappresentante della classe di equivalenza che sceglieremo `e quasi sempre quello semiregolare, ossia il politopo con tutti gli spigoli uguali e le cui facce sono politopi regolari. Questo politopo `e unico a meno di una trasformazione affine. In questa sezione introdurremo uno di questi politopi, il simplesso n-dimensionale, seguendo la notazione in [19].

Definizione 2.9. Sia {e1, . . . , en+1} la base canonica di Rn+1. Il politopo

∆n = conv({e1, . . . , en+1}) `e il simplesso n-dimensionale (o n-simplesso).

Osservazione 2.3. Anche se `_{e contenuto in R}n+1, l’n-simplesso ha dimensione n perch´e ogni ei `e contenuto nell’iperpiano H1 = {(x1, . . . , xn+1)|P xi = 1},

quindi ∆n⊆ H1. Perci`o possiamo dare un’altra definizione di simplesso:

Definizione 2.10. Sia {e1, . . . , en+1} la base canonica di Rn+1. L’n-simplesso

`

e il politopo semiregolare ∆n= {(x1, . . . , xn+1)|P xi= 1, xi ≥ 0 ∀i}.

Figura 2.3: Il simplesso ∆3.

Notazione 2.7. Per convenzione ∆−1= ∅ e ∆0= {e1} ≈ {0}.

Osservazione 2.4. ∆2 `e un triangolo equilatero, ∆3 `e un tetraedro.

Proposizione 2.4. Sia ∆n = conv(e1, . . . , en+1) un simplesso. Allora ogni

j-faccia di un simplesso `e un j-simplesso.

Dimostrazione. Se j = −1 o j = 0 la tesi `e ovvia. Se j > 0, una j-faccia di ∆n `e

un politopo della forma conv({ei1, . . . , eij+1}) ≈ conv({e1, . . . , ej+1}) ≈ ∆j.

Teorema 2.5. Sia Bn+1 = {e1, . . . , en+1} la base canonica di Rn+1, nonch`e

l’insieme dei vertici di ∆n. Allora ∀X ⊆ P(Bn+1), conv(X) `e una faccia di ∆n.

Dimostrazione. Se X = ∅ la tesi `e ovvia. Se X 6= ∅, allora X = {ei1, . . . , eij+1}

e per la Proposizione 2.4 ∆X = {(x1, . . . , xn+1)|P xij = 1, xij ≥ 0 ∀ij} `e

un j-simplesso. Sia HX = {(x1, . . . , xn+1)|P xij = 1} un iperpiano di R

n_:

esso supporta il simplesso ∆n, perch´e ∆nr HX `e contenuto nel semispazio

H_X− = {(x1, . . . , xn+1)|P xij ≤ 1}. Perci`o ∆X = HX ∩ ∆n `e una faccia del

simplesso ∆n ∀X ⊆ P(Bn+1).

Notazione 2.8. Indichiamo con ∆i

n il facet conv({e1, . . . , ei−1, ei+1, . . . , en+1}).

Corollario 2.6. Il reticolo delle facce di ∆n `e isomorfo al reticolo dell’insieme

delle parti di Bn+1, perci`o (F (∆n), ⊇) ∼= (P({1, . . . , n + 1}), ⊇) ∀n ≥ 0. Il

simplesso ∆n ha esattamente n+1_j+1 j-facce, tutte j-simplessi. Inoltre ogni vertice

(19)

2.4 Il permutaedro

In queste due sezioni introdurremo due particolari politopi semplici: il permu-taedro e l’associaedro, seguendo [4] e [5]. Questi due politopi sono, insieme al simplesso, gli elementi pi`u rappresentativi dell’intervallo simplesso-permutaedro. Notazione 2.9. Poniamo [n] = {1, 2, . . . , n} e Snil suo gruppo delle permutazioni.

Definizione 2.11. L’n-permutaedro Pn`e il politopo (con (n + 1)! vertici)

Pn= conv({(σ(1), . . . , σ(n + 1))|σ ∈ Sn+1}) ⊆ Rn+1

Osservazione 2.5. Pn è un politopo n-dimensionale perché è contentuto

intera-mente nell’iperpiano Hn+1= {(x1, . . . , xn+1)|P n+1

i=1 xi = n+1₂ } ⊆ Rn+1.

Figura 2.4: Il 3-permutaedro

Proposizione 2.7. Sia Pn un permutaedro e sia s = (σ(1), . . . , σ(n + 1)) un suo

vertice. Allora esiste uno spigolo tra s ed un vertice t ⇔ t = (i, i + 1) ◦ s ∈ Sn+1.

Quindi Pn `e un politopo semplice ∀n > 0.

Esempio 2.8. Il vertice (1, 2, 3, 4) di P3 `e unito tramite uno spigolo ai vertici

(2, 1, 3, 4), (1, 3, 2, 4), e (1, 2, 4, 3).

Corollario 2.8. Il permutaedro Pn ha n+1₂ spigoli di lunghezza

√

2 ∀n > 0. Osservazione 2.6. ∀n > 0 il permutaedro Pn ha esattamente 2n+1− 2 facet,

perch´e ad ogni facet F possiamo associare un sottoinsieme proprio SF ⊆ [n + 1]

tale che il facet F ha le coordinate nei posti SF pi`u piccole delle altre coordinate.

Esempio 2.9. Al facet F = conv((3, 1, 2, 4), (3, 2, 1, 4), (4, 1, 2, 3), (4, 2, 1, 3)) cor-risponde il sottoinsieme SF = {2, 3} ⊆ [4].

(20)

2.5 L’associaedro

Una prima presentazione combinatoria dell’associaedro risale a Tamari [29]. Fu in seguito realizzato come complesso cellulare da Stasheff in [27] e come politopo in un lavoro non pubblicato di Haiman [20]. Fra i molti lavori dove viene presentata una costruzione dell’associaedro, citiamo Lee [23] (la prima costruzione apparsa in una pubblicazione) e Stasheff-Shnider [28]. Una breve storia e molte realizzazioni sono descritte da Ceballos, Santos e Ziegler in [5]. Noi seguiremo quella di Gelfand, Kapranov e Zelevinsky [18].

Definizione 2.12. Sia Gn+3un (n+3)-agono di area 1, i cui vertici sono indicati

ciclicamente con gli elementi di [n + 3]. Una triangolazione di Gn+3`e una sua

suddivisione in n + 1 triangoli T = {t1. . . . , tn+1} attraverso n diagonali. Il GKZ

vettore della triangolazione T `e: v(T ) =Pn+3

i=1

P

i∈tjArea(tj)ei∈ R

n+3_.

Figura 2.5: Una triangolazione T dell’esagono, con v(T ) = (1₂,1₆, 1,1₆,1₂,2₃)

Definizione 2.13. Per ogni n > 0, l’n-associaedro An `e il politopo convesso

An = conv({v(T )|T `e una triangolazione di Gn+3}) ⊆ Rn+3.

Figura 2.6: Il 3-associaedro

Proposizione 2.9. ∀n > 0, An `e un politopo n-dimensionale con n+11 2n

n

vertici, l’n-esimo numero di Catalan. Ogni coppia di vertici è unita da uno spigolo ⇔ le triangolazioni variano per una diagonale, perciò An è semplice.

Teorema 2.10. ∀n > 0, le j-facce di An sono in bigezione con le triangolazioni

dell’(n + 3)-agono Gn+3 con j − 1 diagonali rimosse. Perci`o An ha n(n−3)

(21)

2.6 I coni

Definizione 2.14. Un cono `_{e un sottoinsieme C di un R-spazio vettoriale V} chiuso rispetto alla moltiplicazione per scalari positivi: v ∈ C, λ > 0 ⇒ λv ∈ C.

Per i coni che incontreremo vale sempre 0 ∈ C e, a meno di isomorfismo, V ⊆ Rn. Per questo motivo useremo la definizione di cono riportata in [2]: Definizione 2.15. Dati A = {v1, . . . , vr} ⊆ Rn, il cono generato da A `e:

σ(A) = {x ∈ V |x = α1v1+ · · · + αrvr, αi∈ R+∪ {0}}

I vettori vi sono detti i generatori del cono ed A `e l’insieme dei generatori.

Esempio 2.10. Siano a = e1− e2e b = e2 in R2 (con la base canonica {e1, e2}).

Il cono generato da C = {a, b} `_{e C = σ(C) = {(x, y) ∈ R}n_{|x ≥ max{0, −y}}:}

Figura 2.7: Il cono C, ombreggiato.

Definizione 2.16. Dato un cono σ, la sua dimensione dim σ `e la dimensione del pi`_{u piccolo R-spazio vettoriale contenente σ.}

Esempio 2.11. Il cono C dell’esempio precedente ha dimensione 2. Osservazione 2.7. Per ogni cono σ(A) si ha che dim σ(A) ≤ |A|.

Esempio 2.12. Se A = ∅, allora σ(∅) = 0 `e il cono zero, di dimensione 0. Notazione 2.10. Chiameremo un insieme N ∼_{= Z}n_{⊆ R}n

un reticolo di Rn_.

Definizione 2.17. Un cono σ `e detto reticolato se tutti i generatori vi di σ

appartengono ad un reticolo N di Rn_.

Osservazione 2.8. Un cono di dimensione n generato da n generatori sar`a sempre reticolato: il suo reticolo `e NA= {x ∈ V |x = α1v1+ · · · + αrvr, αi∈ Z}.

Definizione 2.18. Un cono reticolato σ `e detto puntato o strettamente convesso se 0 ∈ σ e vale che −σ ∩ σ = {0}.

Esempio 2.13. Il cono C = {(x, y) ∈ Rn_{|x ≥ max{0, −y}} dell’Esempio 2.11 `}_e

reticolato per l’osservazione precedente. Inoltre C `e puntato perch´e:

∀(x, y) ∈ (C ∩ −C) ⇒ x ≥ 0 ∧ −x ≥ 0 ⇒ x = 0 ⇒ y ≤ 0 ∧ −y ≤ 0 ⇒ y = 0. Lemma 2.3. Dato A = {v1, . . . , vm} ⊆ Rn, il cono puntato σ(A) ⊆ Rn`e uguale

a Σ(A) = {x ∈ Span(A)|hx, vii ≥ 0 ∀i}, dove h, i `e il prodotto scalare euclideo.

Dimostrazione. x ∈ Σ(A) ⇔ 0 ≤ hx, vii = αi ∀i ⇔ x =P αivi∈ σ(A).

Corollario 2.11. Ogni insieme di generatori A di un cono puntato σ contiene un sottoinsieme minimale di generatori σ, di cardinalit`a dim σ.

Notazione 2.11. D’ora in poi con la parola cono indicheremo un cono puntato σ di dimensione n con un insieme minimale di generatori A = {v1, . . . , vn} ⊆ Rn.

(22)

2.7 Le facce di un cono

Notazione 2.12. ∀A ⊆ Rn _{finito, poniamo M}

A= {v ∈ NA|hv, xi ≥ 0 ∀x ∈ σ}.

Definizione 2.19. Dato un cono σ e un vettore λ ∈ MA, una faccia τ del cono

σ `e l’insieme τ = σ ∩ λ⊥= {v ∈ σ|hv, λi = 0}. Scriveremo che τ < σ.

Esempio 2.14. L’insieme T = {(x, y) ∈ Rn|x = 0, y ≥ 0} `e una faccia del cono C dell’esempio 2.11. Infatti T = σ ∩ (1, 0)⊥ = σ ∩ Span{(0, 1)} con (1, 0) = (0, 1) + (1, −1) ∈ MC e h(x, y), (1, 0)i = x ≥ 0 ∀(x, y) ∈ C.

Osservazione 2.9. σ `e una faccia di se stesso: σ ∩ {0}⊥_{= σ ∩ R}n_{= σ.}

Proposizione 2.12. Dato un cono σ, si ha che: 1. {0} `e una faccia di σ,

2. Ogni faccia τ di un cono σ `e un cono,

3. Ogni intersezione di facce di σ `e una faccia di σ,

4. Ogni faccia di una faccia del cono σ `e a sua volta una faccia del cono σ. Dimostrazione. 1. Sia A = {v1, . . . vn} ⊆ Rnl’insieme dei generatori minimali

di σ. Sia λ = P vi, allora ∀x =P αivi ∈ σ vale che hx, λi =P αi. Per

cui hx, λi = 0 ⇔ αi= 0 ∀i ⇔ x = 0, quindi {0} `e una faccia di σ.

2. Se τ = σ ∩ {λ}⊥, τ `e il cono generato da una base di B = Span(A) ∩ λ⊥. 3. Se τ = σ ∩ {λ}⊥ e ρ = σ ∩ {µ}⊥, per le propriet`a di h, i τ ∩ ρ = σ ∩ (λ + µ)⊥. 4. Se τ = σ ∩ {λ}⊥_{e ρ = τ ∩ {µ}}⊥_{, allora esiste n ∈ N sufficientemente grande}

tale che λ + nµ ∈ σ. Allora per le propriet`a di h, i ρ = σ ∩ (λ + nµ)⊥.

Definizione 2.20. Poich´e una faccia τ di un cono σ `e a sua volta un cono, possiamo definire la dimensione di una faccia τ come la dimensione di τ visto come cono. In modo analogo definiamo la codimensione di una faccia τ

codim τ = dim σ − dim τ

Esempio 2.15. Nel caso dell’Esempio 2.15, la faccia T del cono C `e un cono generato da B = {(0, 1)} che ha dimensione e codimensione uguale a 1.

Definizione 2.21. Una faccia τ di σ diversa da σ e 0 è detta faccia propria. Una faccia τ è detta vertice di σ se è di dimensione 0, spigolo di σ se la sua dimensione è 1, mentre è detta facet di σ se la sua codimensione è 1.

Osservazione 2.10. Un cono ha un unico vertice.

Esempio 2.16. Nel caso dellEsempio 2.15, la faccia T `e uno spigolo ed un facet di C, mentre {0} `e un suo vertice.

Le definizioni di faccia, facet, spigolo e vertice di un cono ricalcano quelle dei politopi. Questa scelta non `e casuale ma suggerisce un collegamento profondo tra i due concetti, che verr`a approfondito nelle prossime sezioni.

(23)

2.8 I fan

Definizione 2.22. Un fan ∆ ⊆ Rn`e un’unione finita di coni tale che: 1. Ogni faccia di un cono di ∆ `e un cono contenuto in ∆,

2. Se σ1e σ2sono coni di ∆, allora σ1∩ σ2`e una faccia comune a σ1 e σ2.

Esempio 2.17. Siano a = e1− e2, b = e2, c = −e1 in R2 (con la base canonica

{e1, e2}), sia D il cono σ(b, c) = {(x, y) ∈ R2|x ≤ 0 ≤ y} e sia C il cono

dell’Esempio 2.11 Allora ∆ = C ∪ D è un fan perché C ∩ D = T = D ∩ (−e1)⊥ è

una faccia comune a entrambi i coni.

Figura 2.8: Il fan ∆ = C ∪ D, ombreggiato.

La definizione di fan e la Proposizione 1.9 implicano il seguente teorema: Teorema 2.13. Le facce dei coni di un fan ∆ formano un reticolo, detto il reticolo delle facce, la cui relazione d’ordine `e il contenimento insiemistico ⊇.

Figura 2.9: Il diagramma di Hasse del reticolo delle facce di ∆.

Definizione 2.23. Un cono affine `_{e un insieme convesso S ⊆ R}n _{tale che}

∃x ∈ Rn _{tale che S − x = {s − x|s ∈ S} `}_{e un cono, detto il cono base di S. Il}

punto x `e il vertice del cono affine S.

Esempio 2.18. A = {(x, y) ∈ R2_{|x ≥ 1, y ≥ 2} `}_{e un cono affine con vertice}

x = (1, 2) e cono base σ({e1, e2}) ⊆ R2.

Teorema 2.14. Ogni politopo P = conv(v1, . . . , vn) ⊆ Rn si pu`o ottenere come

intersezione finita di n coni affini, che hanno vertice nei vertici del politopo: P =

n

\

i=1

σvi = x + σ({vi− vj|j ∈ [n] r {i}})

In verit`a, un politopo P = conv(v1, . . . , vn) di dimensione maggiore di 1 si

pu`o ottenere intersecando soltanto alcuni degli n coni σvi:

Esempio 2.19. ∀n ≥ 2, il simplesso ∆n`e uguale a σe1∩ σe2

Questo esempio ci suggerisce la possibilit`a di ottenere in qualche modo tutti i politopi n-dimensionali dal simplesso. Per alcuni politopi semplici `e possibile farlo con una tecnica, detta troncamento, che tratteremo nella prossima sezione.

(24)

2.9 Il troncamento di un politopo

In questa sezione, seguendo [4], definiremo una tecnica per ottenere politopi semplici da altri politopi semplici: il troncamento di un politopo con un iperpiano. Definizione 2.24. Sia H un iperpiano di Rn

e A ⊆ Rn _{un insieme connesso.}

L’iperpiano H `e sotto A se A ⊆ H−, mentre `e sopra A se A ⊆ H+ Esempio 2.20. La palla B(0, 1) ⊆ R2

sta sopra H = {x ∈ R2_|he

1, xi + 2 = 0}.

Definizione 2.25. Sia P ⊆ Rn _{un politopo e H un iperpiano che non contiene}

alcun vertice di P . P ∩ H+ _{e P ∩ H}− _{sono n-politopi, detti troncamenti di P .}

Esempio 2.21. Il trapezio T = ∆2∩ H−`e ottenuto troncando il simplesso ∆2

con l’iperpiano H, come mostrato in figura:

Figura 2.10: Il trapezio T `e un troncamento del simplesso ∆2.

Proposizione 2.15. Sia P un n-politopo semplice e sia H un iperpiano che non contiene i vertici di P . Allora P ∩ H+ e P ∩ H− sono n-politopi semplici. Dimostrazione. I vertici di P ∩ H+ _{(o P ∩ H}−_{) diversi dai vertici di P sono le}

intersezioni dell’iperpiano H con gli spigoli di P . Poiché P è semplice, ogni suo spigolo è contenuto in n − 1 facet: ogni nuovo vertice di P ∩ H+ _{(o P ∩ H}−_{) `}_e

contenuto in n facet, perci`o P ∩ H+ _{e P ∩ H}− _{sono n-politopi semplici.}

Definizione 2.26. Sia H un iperpiano di Rn _{e P un politopo semplice e G una}

sua faccia propria. L’iperpiano H separa G da P se H separa i vertici di G dagli altri vertici del politopo P e G ⊆ H+_.

Esempio 2.22. Nel caso dell’Esempio 2.21, H separa la faccia {e3} da ∆2.

Proposizione 2.16. Sia H un iperpiano che separa una d-faccia G da un politopo semplice P . Allora P ∩H+≈ G×∆n−d: se G `e un vertice, P ∩H+≈ ∆n.

Il politopo P ∩ H− `e pi`u interessante:

Definizione 2.27. Sia P un n-politopo semplice e G una sua faccia propria. Il troncamento di G da P `e il politopo trG(P ) = P ∩ H−, dove H `e un qualsiasi

iperpiano che separa la faccia G da P .

Osservazione 2.11. Il troncamento di una faccia G da un politopo semplice P è ben definito, perché P ∩ H− è unico a meno di equivalenza combinatoria. Esempio 2.23. Nel caso dell’Esempio 2.21, il trapezio T è il politopo tr{e3}(∆2).

Osservazione 2.12. Se G `e un facet di un politopo semplice S, per la Proposizione 2.17 trG(P ) ≈ P , per cui studieremo i troncamenti delle altre facce proprie.

Gli elementi dell’intervallo simplesso-permutaedro n-dimensionale sono ottenuti troncando diverse volte le facce del simplesso ∆n.

(25)

Capitolo 3

L’intervallo

simplesso-permutaedro

In questo capitolo introdurremo i concetti di ipergrafo [8], building set, nested set e complessi simpliciali [24]. Queste nozioni saranno necessarie per poter definire l’intervallo simplesso-permutaedro nell’ultima sezione.

I nested set sono stati definiti per la prima volta da Fulton e MacPherson in [14], mentre De Concini e Processi [7] hanno introdotto il concetto di building set, generalizzando nel contempo i nested set. Feichtner e Kozlov in [10] hanno poi definito i building set ed i nested set in un modo puramente combinatorio.

I nested set sono stati utilizzati poi per descrivere i reticoli delle facce di una famiglia di politopi semplici da Feichtner e Sturmfels in [11] e Postnikov in [25]. Attraverso la teoria dei modelli reali di De Concini-Processi, Gaiffi in [15] ha ottenuto i nestoedri non lineari, mentre in [16] li ha generati incollando alcune variet`a con angolo. Anche Dosˇen e Petri´c [8] giungono a studiare la stessa famiglia di politopi, questa volta partendo da un approccio induttivo.

In questa tesi, seguendo la strada tracciata da Petrić [24], proveremo l’equiva-lenza tra gli approcci in [11], [25] e [10]: in questo modo si può usare di volta in volta l’approccio più conveniente per descrivere questa famiglia di politopi, estendendo la teoria contenuta in [8].

3.1 Gli ipergrafi

Definizione 3.1. Sia C un insieme di cardinalità finita (anche vuoto). Un ipergrafo di un insieme C è una famiglia di insiemi H ⊆ P(C) che soddisfa le seguenti proprietà:

1. ∅ /∈ H,

2. C `e uguale all’unioneS H di tutti gli elementi di H.

Esempio 3.1. E = {{x, y}, {x, y, z}, {y, z}, {u}, {v}} `e un ipergrafo dell’insieme D =S E = {x, y, z, u, v}.

Notazione 3.1. Poich´e C =S H, quando parliamo di un ipergrafo H possiamo omettere di menzionare l’insieme C.

(26)

Osservazione 3.1. Sia H un ipergrafo di un insieme C. Allora H = ∅ ⇔ C = ∅. Definizione 3.2. Una partizione ipergrafica di un ipergrafo H `e una partizio-ne {H1, . . . , Hn} dell’ipergrafo H (con n ≥ 1) tale che l’insieme {S H1, . . . ,S Hn}

`

e una partizione di C =S H.

Esempio 3.2. Sia E = {{x, y}, {x, y, z}, {y, z}, {u}, {v}} l’ipergrafo dell’Esempio 3.1 Allora l’insieme F = {{{x, y}, {x, y, z}, {y, z}, {u}}, {{v}}} è una partizione ipergrafica di E. Invece G = {{{x, y}, {x, y, z}}, {{y, z}, {u}, {v}}} non lo è, poiché S{{x, y}, {x, y, z}} = {x, y, z} e S{{y, z}, {u}, {v}} = {y, z, u, v}, ma l’insieme {{x, y, z}, {y, z, u, v}} non è una partizione di D =S E = {x, y, z, u, v}. Notazione 3.2. Con il termine partizione indicheremo le partizioni ipergrafiche. Definizione 3.3. Dato un ipergrafo H, la sua partizione banale è ∅ se H = ∅ e {H} altrimenti. Un ipergrafo H si dice connesso se esiste un’unica partizione ipergrafica di H, la partizione banale.

Esempio 3.3. L’ipergrafo L = {{x, y}, {x, y, z}, {y, v}, {z, u}} è connesso, perché l’unica partizione ipergrafica di L è {L}.

Non `e sempre immediato determinare se un ipergrafo `e connesso oppure no. Per ovviare a questo problema introduciamo i grafi delle intersezioni:

Definizione 3.4. Sia H un ipergrafo. Il grafo delle intersezioni di H è il grafo Ω(H) che ha per vertici gli elementi di H. Ogni coppia di elementi di H è collegata da un arco ⇔ la loro intersezione è non vuota. Un cammino di H è un insieme X1, . . . , Xn, di n ≥ 1 elementi distinti di H che formano un cammino

di Ω(H). ∀x, y ∈S H, un cammino di H unisce x con y se x ∈ X1 e y ∈ Xn.

Esempio 3.4. Sia E = {{x, y}, {x, y, z}, {y, z}, {u}, {v}}. {x, y}, {x, y, z} `e un cammino di E che unisce x e z. Il grafo delle intersezioni di E `e:

Figura 3.1: Il grafo Ω(E).

Proposizione 3.1. Un ipergrafo H `e connesso ⇔ il grafo Ω(H) `e connesso ⇔ ∀x, y ∈S H esiste un cammino di H che unisce x e y.

Esempio 3.5. L’ipergrafo E dell’Esempio 3.1 non `e connesso.

Definizione 3.5. Una partizione H0 = {H1, . . . , Hn} di un ipergrafo H si

dice raffinata se ogni Hi `e un ipergrafo connesso di S Hi. Allora ∀i, S Hi

`

e una componente connessa di S H e il numero n = |H0_{| `}_{e il numero di}

connessione di H.

Osservazione 3.2. Le componenti connesse di un ipergrafo H sono le componenti connesse dell’ipergrafo Ω(H).

Esempio 3.6. E0_{= {{{x, y}, {x, y, z}, {y, z}}, {{u}}, {{v}}} `}_{e la partizione}

raffi-nata dell’ipergrafo E dell’Esempio 3.1 : il suo numero di connessione `e 3. Proposizione 3.2. Ogni ipergrafo H ammette un’unica partizione raffinata H0. Corollario 3.3. Un ipergrafo H 6= ∅ `e connesso ⇔ H0= {H}.

(27)

3.2 I complessi simpliciali

Definizione 3.6. Sia {α1, . . . , αn} una famiglia di insiemi finiti incompatibili

per inclusione, ossia tali che @i, j per cui αi ⊆ αj: gli insiemi αi sono detti

basi. Allora C = P(α1) ∪ · · · ∪ P(αn) `e un complesso simpliciale finito

astratto: {α1, . . . , αn} `e l’insieme delle basi di C.

Esempio 3.7. Sia α1= {x, y, z} e α2= {x, y, u}, allora C = P(α1) ∪ P(α2):

C = {

P(α1)

z }| {

{z}, {x, z}, {y, z}, {x, y, z}, ∅, {x}, {y}, {x, y}, {u}, {x, u}, {y, u}, {x, y, u}

| {z }

P(α2)

}

`e un complesso simpliciale finito astratto, con insieme delle basi {α1, α2}.

Notazione 3.3. Per alleggerire la notazione, d’ora in poi ci si riferir`a ai complessi simpliciali finiti astratti semplicemente come complessi simpliciali. In base al contesto, ci si riferir`a ad essi come insiemi, semireticoli o poset.

Osservazione 3.3. Come l’insieme delle parti, un complesso simpliciale C `e un semireticolo inferiore (C, ⊆), il cui operatore meet `e l’intersezione ∩.

Notazione 3.4. Data una funzione f : A → B, indicheremo con f [A] l’insieme {f (a)|a ∈ A} e analogamente ∀C ⊆ A, indicheremo con f [C] = {f (c)|c ∈ C}. Lemma 3.1. Due complessi simpliciali C e D sono isomorfi come semireticoli (o come poset) ⇔ esiste una bigezione φ :S C → S D tale che α ∈ C ⇔ φ[α] ∈ D. Definizione 3.7. Una funzione ψ induce l’isomorfismo tra C e D se ψ|∪C ≡ φ.

Proposizione 3.4. Dato C un complesso simpliciale ed una funzione ψ tale che la sua restrizione aS C sia bigettiva, allora ψ induce un isomorfismo tra C ed il complesso simpliciale {ψ[α]|α ∈ C}.

Corollario 3.5. Siano C, D1 e D2 tre complessi simpliciali: se una funzione

ψ induce un isomorfismo tra C e D1 e tra C e D2, allora D1= D2.

3.3 I building set

In questa sezione introdurremo l’argomento cardine di tutta questa trattazione: i building set. Come spiegato all’inizio del capitolo, seguiremo le definizioni e l’approccio di Petrić (contenuto in [24]) e Doˇsen e Petrić (contenuto in [8]). Definizione 3.8. Un ipergrafo H si dice atomico se ∀x ∈S H ⇒ {x} ∈ H. Esempio 3.8. P = {{x, y}, {x}, {y}, {z}} è un ipergrafo atomico dell’insieme S P = {x, y, z}, mentre H = ∅ è l’ipergrafo atomico di ∅.

Notazione 3.5. Dati H ⊆ P(C) e B ⊆ C, indicheremo con HB la famiglia di

insiemi HB= {X ∈ H|X ⊆ B} = H ∩ P(B).

Lemma 3.2. Un ipergrafo H `e atomico ⇔ ∀Y ⊆S H, HY `e un ipergrafo di Y .

Corollario 3.6. Se H `e un ipergrafo atomico e Y ⊆ S H, allora HY `e un

(28)

Definizione 3.9. Un ipergrafo H si dice saturato se ∀β, γ ∈ H tali che β ∩ γ 6= ∅, si ha che β ∪ γ ∈ H.

Esempio 3.9. M = {{x, y}, {x, z}, {x, y, z}} e ∅ sono ipergrafi saturati.

Definizione 3.10. Dato un insieme finito α, una famiglia B di sottoinsiemi di α si dice building set di P(α) se `e un ipergrafo atomico saturato di P(α). Se α ∈ B, allora B `e detto un α-building set di P(α).

Esempio 3.10. Dato un insieme α = {x, y, z, w}, un building set di P(α) `e: Bα= {{x}, {y}, {z}, {w}

| {z }

atomico

, {x, y}, {y, z}, {z, w}, {x, y, z}, {y, z, w}, {x, y, z, w}

| {z }

saturato

}

Osservazione 3.4. ∅ `e l’unico building set di ∅.

Lemma 3.3. Dato un insieme finito α, B `e un α-building set ⇔ B `e un ipergrafo atomico saturato connesso di P(α).

Esempio 3.11. Bα`e un α-building set di P(α).

Lemma 3.4. Sia α un insieme finito e non vuoto e B `e un building set di α. ∀γ ⊆ α non vuoto si ha che Bγ = B ∩ P(γ) `e un building set di P(γ).

Dimostrazione. Basta provare che Bγ sia un ipergrafo atomico saturato di P(γ):

• ∀c ∈ γ ⊆ α, {c} ∈ B perch´e `e un ipergrafo atomico: {c} ∈ Bγ= B ∩ P(γ)

∀c ∈ γ. Quindi S Bγ ⊇S{{c}|c ∈ γ} = γ e ∅ /∈ Bγ perch´e ∅ /∈ B, perci`o

Bγ `e un ipergrafo di P(γ), ed `e atomico per l’osservazione precedente.

• ∀b, c ∈ Bγ = B ∪ P(γ) tali che b ∩ c 6= ∅, si ha che b ∪ c ∈ B ∪ P(γ) = Bγ,

perché B è un ipergrafo saturato e b, c ∈ P(γ) ⇒ b ∪ c ∈ P(γ). Bγ è un ipergrafo atomico saturato di P(γ), ossia è un suo building set.

Corollario 3.7. Se α `e un insieme finito tale che |α| ≥ 2, allora gli α-building set formano il reticolo (H(α), ⊆) (dove l’operatore ∧ `e l’intersezione): in questo reticolo si ha che min H(α) = {{a}|a ∈ α} ∪ {α}, mentre max H(α) = P (α) r ∅. Esempio 3.12. Sia α = {x, y, z}. Allora min H(α) = {{x}, {y}, {z}, {x, y, z}}, mentre max H(α) = P (α) r ∅ = {{x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}

Il concetto di building set si pu`o estendere anche ai complessi simpliciali: Definizione 3.11. Sia C un complesso simpliciale con basi {α1, . . . , αn}. B ⊆ C

`

e un building set di C se Bαi= B ∩ P(αi) `e un building set di P(αi) ∀i.

Esempio 3.13. Sia α1 = {x, y, z}, α2 = {x, y, u}, e C = P(α1) ∪ P(α2) un

complesso simpliciale. Un building set del complesso simpliciale C `e:

BC= {

B_α1=B ∩ P(α1)

z }| {

{z}, {y, z}, {x, y, z}, {x}, {y}, {x, y}, {u}, {x, u}, {x, y, u}

| {z }

B_α2=B ∩ P(α2)

}

(29)

I building set dei complessi simpliciali sono intimamente collegati con quelli dei loro sottoinsiemi. Infatti i building set soddisfano le seguenti proprietà: Proposizione 3.8. Dato un insieme finito e non vuoto α ed un complesso simpliciale C, si ha che: 1. P(α) r {α} è un complesso simpliciale. 2. B è un building set di C ⇔ Bγ = B ∩ P(γ) lo è di P(γ) ∀γ ∈ C; 3. B `_{e un building set di P (α) ⇒ B r {α} lo è di P(α) r {α};} 4. B⊥= {{γ}|γ ∈ C} r {∅} è un building set di C; 5. Se α ∈ C ⇒ B⊥∪ {α} è un building set di C;

6. Se B `_{e un building set di C e β ∈ min(B r B}⊥), allora l’insieme B r {β}

`

e un building set di C;

7. Se B `_{e un building set di C e β ∈ max(C r B), allora l’insieme B ∪ {β} `e} un building set di C.

Dimostrazione. Poniamo C = P(α1) ∪ · · · ∪ P(αn) e α = α1= {a1, . . . , ap}:

1. ∀j ∈ {1, . . . , p} sia Aj= α r {aj}. Allora C = P(α) r {α} =S p

j=1P(Aj),

perci`_{o C = P(α) r {α} `e un complesso simpliciale.}

2. ⇐ `e ovvia, perch´e αi∈ C ∀i. Viceversa ∀γ ∈ C ∃αi ∈ C tale che γ ⊆ αi.

Per definizione Bαi `e un building set di P(αi): per atomicit`a e saturazione

Bγ= Bαi∩ P(γ) = B ∩ P(γ) `e un building set di P(γ), da cui ⇒.

3. Basta porre C = P(α) r {α} e applicare i punti 1 e 2.

4. B⊥ `e ovviamente un ipergrafo atomico di C. Inoltre tutti gli elementi

di B⊥ hanno intersezione vuota, perci`o B⊥ `e un ipergrafo saturato di C.

Quindi B⊥ `e un building set di C.

5. B = B⊥∪ {α} `e un ipergrafo atomico di C per il punto precedente. Inoltre

∀c ∈ B, c ∩ α 6= ∅ ⇔ c ⊆ α. Perciò B è un ipergrafo saturato di C, quindi B⊥è un building set di C.

6. Poich´_{e B r {β} ⊇ B}⊥, B r {β} `e un ipergrafo atomico di C per il punto

4. Inoltre B r {β} è saturato, perché per minimalità di β @b, c ∈ B r {β} tali che b ∪ c = β e b ∩ c 6= ∅. Quindi B r {β} è un building set di C. 7. Senza perdita di generalità β ⊆ α. Poiché B ∪ {β} ⊇ B⊥, B ∪ {β} è un

ipergrafo atomico di C per il punto 4. Inoltre B ∪ {β} è saturato, perché per massimalità di β ∀c ∈ B ∪ {β} tale che β ∩ c 6= ∅ si ha che β ∪ c = α. Perciò B ∪ {β} è un building set di C.

Questa proposizione sar`a il punto di partenza per lo studio dei building set e dei loro sottoinsiemi. Alcuni di questi sottoinsiemi, i nested set, saranno l’argomento della prossima sezione.

(30)

3.4 I nested set

Definizione 3.12. Data una famiglia di insiemi N , β = {β1, ..., βn} ⊆ N (con

n ≥ 2) `e una N -anticatena se {β1, ..., βn} sono incompatibili per inclusione.

Data una famiglia di insiemi M , β manca M se β1∪ ... ∪ βn∈ M ./

Esempio 3.14. Dato α = {x, y, z, w}, β = {{x}, {z, w}} `e una P(α)-anticatena poich´e {x} 6⊆ {z, w} e {z, w} 6⊆ {x}. La P(α)-anticatena β manca l’α-building set Bα= {{x}, {y}, {z}, {w}, {x, y}, {y, z}, {z, w}, {x, y, z}, {y, z, w}, {x, y, z, w}},

perch´e {x} ∪ {z, w} = {x, z, w} /∈ Bα.

Definizione 3.13. Dato un α-building set B di P (α), N ⊆ B `e un nested set di B se ogni N -anticatena β manca l’α-building set B.

Esempio 3.15. Sia Bα come nell’esempio precedente. Nα= {{x}, {z}, {z, w}}

`

e un nested set di Bα perch´e entrambe le Nα-anticatene β1 = {{x}, {z, w}} e

β2= {{x}, {z}} mancano il building set Bα.

Osservazione 3.5. ∀b ∈ B, {b} è un nested set di B poiché {b} non contiene nessuna B-anticatena per questioni di cardinalità.

Come nel caso dei building set, anche il concetto di nested set si pu`o estendere ai building set dei complessi simpliciali:

Definizione 3.14. Dato B un building set di un complesso simpliciale C, N ⊆ B `

e un nested set di B se ∀N -anticatena {β1, . . . , βt}, β1∪ · · · ∪ βt∈ C r B.

Esempio 3.16. Sia α1 = {x, y, z}, α2 = {x, y, u} e sia C = P(α1) ∪ P(α2).

Prendiamo BC = {{x}, {y}, {z}, {u}, {x, y}, {y, z}, {x, u}, {x, y, z}, {x, y, u}} un

building set del complesso simpliciale C. NC = {{x}, {z}} ⊆ BC `e un nested

set di BC, poich´e per l’unica NC-anticatena possibile βC = {{x}, {z}} vale che

{x} ∪ {z} = {x, z} ∈ C r BC.

Lemma 3.5. Sia B un building set di un complesso simpliciale C, N un suo nested set B. ∀M ⊆ N ⊆ B, anche M `e un nested set di B.

Dimostrazione. Poiché M ⊆ N , tutte le M -anticatene sono anche N -anticatene, quindi tutte le M -anticatene mancano il building set B. Perciò M è un nested set di B.

Esempio 3.17. Presi Nαe Bαcome nell’Esempio 3.15, Mα= {{x}, {z, w}} ⊆ Nα

`

e un nested set di Bα

Corollario 3.9. Dato B un building set di un complesso simpliciale C, i nested set di B formano un complesso simpliciale, il cui insieme delle basi `e formato dai nested set massimali di B.

Definizione 3.15. Questo complesso simpliciale prende il nome di complesso dei nested set di B e lo indicheremo con ˜N (C, B).

Notazione 3.6. Sia α un insieme finito e non vuoto. Nel caso in cui C = P(α) indicheremo il complesso dei nested set di un C-building set B con Ñ (P(α), B). Definizione 3.16. Sia C un complesso simpliciale. Possiamo definire il com-plesso di nested set dell’insieme D = C r {∅}, ponendo Ñ (D, B) = Ñ (C, B).

(31)

Osservazione 3.6. Poich´e ∀β ∈ B {β} `e un nested set di B,S _˜

N (C, B) = B. Questa osservazione permette di provare facilmente la seguente proposizione: Proposizione 3.10. Dato B un building set di un complesso simpliciale C ed N un suo nested set, sono equivalenti i seguenti fatti:

1. N ∈ ˜N (C, B);

2. N ⊆ B,S N ∈ C e ogni N -anticatena manca B; 3. ∃γ ∈ C tale che N ∈ ˜N (P (γ), Bγ), con Bγ = B ∩ P(γ);

4. ∃ una base α di C tale che α ∈ B e N ∈ ˜N (P (α), Bα), con Bα= B ∩ P(α).

Dimostrazione. Otteniamo la tesi provando le seguenti implicazioni: 1. ⇔ 2. Ovvio per la definizione di nested set.

2. ⇔ 4. Ovvio per la definizione di nested set di un complesso simpliciale. 4. ⇒ 3. Ovvio, perch´e basta porre γ = α.

3. ⇒ 4. ∀γ ∈ C ∃ una base α di C tale che γ ∈ α. Allora ∃Bα= B ∩ P(α) building

set tale che Bα ⊇ Bγ. Poich´e tutte le N -anticatene mancano Bγ, esse

mancano anche il building set Bα: N `e un nested set di Bα, da cui la tesi.

Corollario 3.11. Sia C un complesso simpliciale e B un suo building set connesso. Allora ( Ñ (C, B), ⊆) è un reticolo ordinato dall’inclusione insiemistica. In particolare ( Ñ (C, B), ⊆) ha come massimo B e come minimo ∅.

Osservazione 3.7. I risultati precedenti valgono anche nel caso in cui C = D r ∅, (dove D `e un complesso simpliciale).

I reticoli dei nested set rivestiranno un ruolo fondamentale nello studio dei politopi semplici. Proveremo infatti che per ogni politopo semplice esiste un reticolo di nested set isomorfo all’opposto del reticolo delle facce del politopo: otterremo cos`ı una classificazione, a meno di equivalenza combinatoria.

3.5 Le costruzioni

Definizione 3.17. Dato H un ipergrafo atomico, una costruzione di H, definita induttivamente su |S H|, `e un insieme K tale che:

(C0) se |S H| = 0, H = ∅ ⇒ K = ∅,

(C1) se |S H| ≥ 1 e H `e connesso, ∀x ∈ S H se Kx `e una costruzione di

H_{S Hr{x}}, allora K = Kx∪ {S H} `e una costruzione di H,

(C2) se |S H| ≥ 2 e H non `e connesso, con {H1, . . . , Hn} la partizione raffinata

di H (quindi n ≥ 2), se ∀i ∈ {1, . . . , n}, Ki`e una costruzione di Hi, allora

K1∪ · · · ∪ Kn `e una costruzione di H.

(32)

Osservazione 3.8. Per ogni costruzione K vale che |K| = |S H|.

Esempio 3.18. Siano A = {{x}, {y}, {z}, {u}, {x, y}, {y, z}, {z, u}, {x, y, z}} ed A00_{= A r {x, y, z} ipergrafi atomici di γ = {x, y, z, u}. Una costruzione di A `e:}

M = {{y}, {u}, {y, z, u}, {x, y, z, u}} La costruzione M `e ottenuta induttivamente in questo modo:

1. Iniziamo per (C0) con M0= ∅, una costruzione dell’ipergrafo ∅,

2. Ora per (C1) M1= M0∪ {{u}} = {{u}} `e una costruzione dell’ipergrafo

{{u}} e M2= M0∪ {{y}} = {{y}} `e una costruzione di {{y}},

3. Poi, applicando (C2), abbiamo M3 = M1∪ M2 = {{y}, {u}} `e una

costruzione dell’ipergrafo non connesso {{y}, {u}}

4. Quindi, applicando (C1), si ha M4= M3∪{{y, z, u}} = {{y}, {u}, {y, z, u}},

una costruzione di A0 = {{y}, {z}, {u}, {y, z}, {z, u}}

5. Infine, applicando ancora (C1), otteniamo M come M = M4∪{{x, y, z, u}}.

Per (C1), M `e una costruzione anche dell’ipergrafo A00.

Gli ipergrafi non sono univocamente determinati dalle loro costruzioni, come mostrato dall’esempio precedente. Vogliamo perci`o trovare una relazione di equivalenza tra gli ipergrafi atomici che hanno lo stesso insieme delle costruzioni: essa sar`a definita nella Sezione 3.6, in particolare dal Teorema 3.15.

Per fare questo, introdurremo il concetto di chiusura saturata di un ipergrafo: Definizione 3.18. Dato un ipergrafo H, la sua chiusura saturata ¯H `e il pi`u piccolo ipergrafo saturato contenente H.

Osservazione 3.9. Se H è un ipergrafo atomico, allora ¯H è un building set. Se H è un building set, per saturazione si ha che ¯H = H.

Esempio 3.19. Gli ipergrafi A, A00 dell’Esempio 3.18 hanno la chiusura saturata: ¯

A = {{x}, {y}, {z}, {u}, {x, y}, {y, z}, {z, u}, {x, y, z}, {y, z, u}, {x, y, z, u}} = ¯A00

Per dimostrare che un ipergrafo `e saturato, useremo spesso questo lemma: Lemma 3.6. Un ipergrafo H `e saturato ⇔ vale una delle seguente ipotesi:

1. ∀Y ⊆S H, se HY r {Y } `e un ipergrafo connesso di Y , allora Y ∈ H; 2. ∀Y ⊆S H, se HY `e un ipergrafo connesso di Y , allora Y ∈ H;

3. ∀Y ⊆S H, HY `e un ipergrafo connesso di Y ⇔ Y ∈ H.

Dimostrazione. Poiché l’ipotesi 3. implica le altre due, è sufficiente provare il lemma per l’ultimo punto. Inoltre l’ipotesi 3. implica che l’ipergrafo H sia saturato: resta da provare il viceversa. Sia H un ipergrafo saturato e sia Y ⊆S H. Se Y ∈ H, allora la saturazione di H implica che HY è un ipergrafo

connesso di Y . Viceversa, se ∃Y ∈ H tale che HY `e un ipergrafo non connesso,

(33)

3.6 Gli ipergrafi affini

Questa sezione, seguendo [8], vuole rispondere all’interrogativo che ci siamo posti nella sezione precedente, ossia se esiste una relazione di equivalenza tra gli ipergrafi atomici che hanno lo stesso insieme delle costruzioni.

Definizione 3.19. Dato un insieme C finito e non vuoto, due ipergrafi atomici H1 e H2 di C si dicono affini se hanno la stessa chiusura saturata.

Esempio 3.20. Gli ipergrafi A e A00dellEsempio 3.18 sono affini.

Osservazione 3.10. Essere affini `e una relazione di equivalenza: ogni classe di equivalenza [H] contiene un unico building set, la chiusura saturata ¯H. Perci`o ∀H ipergrafo atomico si ha che ¯H = ¯¯ H.

Notazione 3.7. Indicheremo due ipergrafi H1, H2 affini con il simbolo H1∼ H2.

In questa sezione proveremo che ”essere affini” `e proprio la relazione cercata. Definizione 3.20. Dato un ipergrafo H, un insieme Y ⊆S H si dice superfluo in H se HY r {Y } `e un ipergrafo connesso di Y .

Osservazione 3.11. Un singoletto diS H non sarà mai un insieme superfluo Esempio 3.21. Sia F = {{x, y}, {y, z}, {u}, {v}}: {x, y, z} è superfluo in F . Osservazione 3.12. Per il Lemma 3.6, un ipergrafo H è saturato se ogni suo

insieme superfluo `e un elemento di H.

Proposizione 3.12. Sia Y un insieme superfluo in un ipergrafo H. Allora: 1. Z `e superfluo in H ⇔ Z `e superfluo in H ∪ {Y },

2. H `e connesso ⇔ H ∪ {Y } `e connesso.

Dimostrazione. Proviamo il punto 1. L’implicazione destra `e ovvia. Per l’altra, supponiamo che Z sia superfluo in H ∪ {Y }. Allora (H ∪ {Y })Zr {Z} `e connesso. Se Y 6⊆ Z, (H ∪ {Y })Z = HZ ed abbiamo la tesi. Se Y ⊆ Z, ∀x, y ∈ Z per la

Proposizione 3.1 esiste un cammino X1, . . . , Xn di (H ∪ {Y })Zr {Z} che unisce x a y, perci`o x ∈ X1e y ∈ X2. Se Xi6= Y ∀i ∈ [n], X1, . . . , Xn `e un cammino

di HZr {Z}, da cui la tesi. Se ∃i ∈ [n] tale che Xi6= Y , abbiamo 3 casi:

(P1) Se 1 < i < n, il cammino `e della forma X1, . . . , Xi−1, Y, Xi+1, . . . , Xn. Sia

x0∈ Xi−1∩ Y un punto unito ad x dal cammino X1, . . . , Xi−1di HZr {Z} e sia y0 ∈ Xi+1∩ Y un punto unito ad y dal cammino Xi+1, . . . , Xn di

HZr {Z}. Poiché Y è superfluo, HY r {Y } è connesso. Per il Lemma 3.6 esiste un cammino Y1, . . . , Ymdi HY r {Y } che unisce x0 con y0. ∀j ∈ [m] Yj ⊂ Y ⊆ Z, perciò Y1, . . . , Ym è un cammino di HZ r {Z}. Perciò X1, . . . , Xi−1, Y1, . . . , Ym, Xi+1, . . . , Xn (a meno di rimuovere qualche suo

elemento) `e un cammino di HZr {Z} che unisce x e y, da cui la tesi. (P2) Se 1 = i < n, basta porre x0= x e seguire (P1).

(P3) Se 1 ≤ i = n, basta porre y0= y e seguire (P1).

Per il punto 2., l’implicazione destra `e ovvia. Per l’altra, basta percorrere la dimostrazione del punto 1. prendendo il cammino X1, . . . , Xn in H ∪ {Y }. Il