Combinatoria

János Körner Claudia Malvenuto 26 settembre 2004

2

Prefazione

Caro Lettore,

gli appunti di queste pagine contengono tutto il materiale spiegato durante le lezioni e parte del materiale relativo alle esercitazioni del corso Matematica Discreta 1: Combinatoria impartito per il Corso di Laurea in Informatica dell’Università di Roma "La Sapienza". Il materiale è stato scelto quasi integralmente dai primi capitoli dell’eccellente libro di J. H. van Lint e R. M. Wilson, A Course in Combinatorics [14]. Il libro di van Lint e Wilson nasce dalle loro lezioni presso il "California Institute of Technology". Bisogna ammettere che il testo di van Lint-Wilson è destinato ad un pubblico che possiede una maggiore esperienza matematica di quella di uno studente di secondo anno del nostro Corso di Laurea. Questo spiega però solo in parte il carattere compatto delle dimostrazioni fornite dagli autori di [14]. La forma abbozzata delle loro dimostrazioni è soprattutto frutto della loro ambizione di costringere lo studente ad una lettura autonoma, attiva ed approfondita del loro libro. Ciò significa che il lettore deve completare il testo delle loro dimostrazioni, come e più di quanto si fa solitamente per risolvere i familiari esercizi nei libri di grammatica. Difatti la matematica non si capisce leggendo un testo con le mani in mano. È quindi con molta esitazione e quasi "malvolentieri" che si offre oggi alla lettura dei nostri studenti il seguente testo in cui ogni dubbio lasciato aperto, ogni piccolo salto logico del libro [14] è cancellato. Lo studente che malauguratamente fosse interessato solo a superare l’esame di Combinatoria senza cercare di capire la materia potrebbe essere tentato di memorizzare questo testo. Nulla di più sbagliato.

Naturalmente, non ci siamo limitati a "completare" le dimostrazioni in [14]. In alcuni casi le abbiamo modificate, e inoltre abbiamo aggiunto altro materiale (come per esempio quello sulla decomposizione ciclica delle permutazioni.) Il nostro testo non ha certo l’ambizione di essere un libro sulla Combinatoria. L’esposizione segue quasi pedissequamente le deduzioni matematiche esposte alla lavagna durante il corso e i commenti rimangono essenziali. È nostra ferma convinzione che un corso introduttivo non deve limitarsi alla presentazione di fatti e dimostrazioni elementari, con il rischio di banalizzare la materia. Al contrario, per convincere lo studente del potere e della bellezza dei metodi e dei risultati della combinatoria, è indispensabile "sorprenderlo" e poi coinvolgerlo in imprese matematiche serie. Abbiamo quindi preferito alla redazione di un catalogo enciclopedico di concetti e lemmi elementari e di routine l’esposizione di pochi risultati e metodi importanti. Anzi, abbiamo utilizzato proprio questi risultati per introdurre alcuni dei più salienti concetti della combinatoria in un contesto dimostrativo che li mette alla ribalta. Il materiale qui presentato non è esposto a lezione tutti gli anni. Di anno in anno, sarà il programma del Corso a specificare quella parte del testo che si deve studiare per l’esame.

La teoria combinatoria è il principale strumento matematico di quella parte dell’informatica teorica che riguarda la costruzione di algoritmi e l’analisi della loro complessità. Eppure in Italia non tutti i corsi di laurea in informatica offrono un corso di combinatoria. Il nostro manoscritto è poco più che un invito a insegnare e studiare questa materia, rivolta a studenti di informatica e matematica. Questa ne è la prima versione, ed è destinata a crescere, anche con il vostro aiuto. Ogni commento e critica è decisamente benvenuto, anche qualora si limiti soltanto a segnalarci gli inevitabili errori di stampa.

Vogliamo ringraziare Gabriele Mambrini il quale, producendo un primo manoscritto in L^{A}TEX di appunti di questo corso, ha fornito un canovaccio e uno stimolo di partenza per la redazione del presente testo; gli studenti Cecilia di Chio e Fabio Martinelli per aver messo a disposizione le fotocopie dei loro appunti, presi durante l’anno accademico 2000/01. Ringraziamo inoltre il dott. Daniele A. Gewurz che dopo aver letto con estrema attenzione (e pignoleria!) questo testo ci ha segnalato vari refusi e suggerito utili modifiche.

János Körner^{1} Claudia Malvenuto^{2}

1korner@di.uniroma1.it

2claudia@di.uniroma1.it

Indice

Prefazione i

1 Grafi 1 1.1 Concetti fondamentali sui grafi . . . . . . . . . . . . . . . . . . . . . 1 1.2 Connessione, distanza . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Circuiti euleriani . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Connessione e numero di archi . . . . . . . . . . . . . . . . . . . . . 9 1.5 Algoritmo di Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Alberi, foreste e permutazioni 15 2.1 Formula di Cayley . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Il codice di Prüfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Vertebrati e formula di Cayley . . . . . . . . . . . . . . . . . . . . . 19 2.4 Coefficienti multinomiali . . . . . . . . . . . . . . . . . . . . . . . . 25 2.5 Dimostrazione ricorsiva della formula di Cayley . . . . . . . . . . . 32 2.6 Ordinamenti e permutazioni . . . . . . . . . . . . . . . . . . . . . . 36

3 Colorazione di grafi 43 3.1 Alcune definizioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2 Grafi bipartiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3 Numero cromatico, numero di stabilità, grado . . . . . . . . . . . . . 47 3.4 Il Teorema di Brooks . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.5 Il Teorema di Erdős . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4 Combinatoria estremale 57 4.1 Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2 Famiglie di insiemi ovvero ipergrafi . . . . . . . . . . . . . . . . . . 60

5 Tecniche di conteggio 69 5.1 Il principio di inclusione–esclusione . . . . . . . . . . . . . . . . . . 69 5.2 Applicazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 iv INDICE

Capitolo 1

Grafi

1.1 Concetti fondamentali sui grafi

Se n è un intero positivo, denotiamo con [n] l’insieme degli interi compresi tra 1 ed n:

[n] = {1, 2, …, n}.

L’insieme delle parti di A verrà qui denotato da

2^{A} = {B : B ⊆ A}.

Se A è un insieme e k è un numero naturale, indichiamo con \binom{A}{k} la famiglia di tutti i sottoinsiemi di A di cardinalità k:

\binom{A}{k} = \{B : B ⊆ A, |B| = k\}.  (1.1)

Un grafo semplice e finito G è una coppia di insiemi finiti astratti G = (V (G), E(G)) collegati dalla relazione

E(G) ⊆ \binom{V (G)}{2}.

Gli elementi di V (G) sono chiamati vertici del grafo e le coppie non ordinate di vertici distinti di V (G) che sono in E(G) sono dette archi di G. Due vertici x e y sono adiacenti se la coppia non ordinata {x, y} è un arco. Un vertice x è incidente ad un arco e se x ∈ e. Se e = {x, y}, i vertici x e y si chiamano gli estremi dell’arco e. Spesso si rappresenta un grafo disegnando su un piano un punto distinto per ogni vertice, e collegando con una linea due vertici adiacenti. Ad esempio, il grafo G sui vertici V (G) = {a, b, c, d, e} in cui E(G) = {{a, b}, {a, c}, {a, d}, {b, e}, {b, d}} può essere visualizzato nel seguente modo:

[figure: •; d; •; c; •; a; •; b; •; e; G]

Si deve notare che il punto di intersezione dei segmenti che rappresentano gli archi {a, c} e {b, d} non è un vertice. In questo contesto però ci interessa studiare il grafo da un punto di vista astratto, ovvero solo rispetto alle relazioni di incidenza, e non le sue particolari immersioni nel piano.

La dicitura grafo semplice è un riferimento implicito ad un concetto più generale di grafo, in cui E(G) è un cosiddetto multinsieme di coppie non ordinate di elementi di V (G). Se i due elementi di una coppia non sono distinti, l’arco {x, x} si chiama cappio su x. Se l’arco {x, y} è presente in E(G) con molteplicità m superiore ad 1, si parla di m archi paralleli \{x, y\}. Un grafo G è completo se E(G) = \binom{V (G)}{2}, ovvero se tutti i vertici sono collegati tra loro. Il grafo completo su n vertici verrà denotato da K_{n}. Un grafo G in cui E(G) = ∅ si dice totalmente sconnesso e si può indicare con E_{n}.

[figure: •; 4; •; 3; •; 1; •; 2; K_{4}; •; 4; •; 3; •; 1; •; 2; E_{4}]

(Digressione. Un ipergrafo H è una coppia ordinata (V (H), E(H)), ove V (H) è un insieme finito, detto insieme di vertici dell’ipergrafo, ed E(H) ⊆ 2^{V (H)} è una famiglia di sottoinsiemi di V (H), detti iperarchi. Nel caso in cui tutti gli iperarchi abbiano la stessa cardinalità si parla di ipergrafo uniforme.)

Due grafi G e H sono isomorfi se esiste una biiezione f : V (G) → V (H) dei vertici che conservi le adiacenze, i.e. tale che

{a, b} ∈ E(G) ⇔ {f(a), f(b)} ∈ E(H).

Tale biiezione f è un isomorfismo dei grafi G ed H. Un grafo G′ è un sottografo di G se V (G′) ⊆ V (G) ed E(G′) ⊆ E(G). G′ è un sottografo ricoprente di G (o di copertura; in inglese: spanning subgraph) se V (G) = V (G′). G′ è un sottografo indotto di G (in inglese: induced o spanned subgraph) se E(G′) = E(G) ∩ \binom{V (G′)}{2}. Se A ⊆ V (G), si può indicare con G[A] il sottografo indotto in G dall’insieme A di vertici. Per ottenere da un grafo un sottografo di copertura si eliminano archi, ma non vertici; per ottenere un sottografo indotto si eliminano vertici (e perciò gli archi ad essi adiacenti), ma non si eliminano gli archi adiacenti ai vertici rimanenti. Nella figura seguente, G rappresenta un grafo, G′ un suo sottografo di copertura, G′′ un suo sottografo indotto.

G•  • •  •  • •  G′•  • •  •  • •  G′′  • •  •  •

Se x ∈ V (G), l’intorno di x è il sottoinsieme Γ(x) dei vertici adiacenti a x:

Γ(x) = {y : y ∈ V (G), {x, y} ∈ E(G)} .

Il grado di un vertice x è il numero di vertici ad esso adiacenti e si denota con d_{G}(x) = |Γ(x)|. Un vertice x si dice isolato se d_{G}(x) = 0. Il grado del grafo G è

d(G) = max_{x∈V (G)} d_{G}(x).

Un grafo si dice regolare se tutti i suoi vertici hanno lo stesso grado.

La relazione che lega i gradi dei vertici e il numero di archi di un grafo è espressa nel seguente:

Lemma 1.1

∑_{x∈V (G)} d_{G}(x) = 2|E(G)|  (1.2)

Dimostrazione. Questa dimostrazione usa la tecnica del doppio conteggio. Sia

A = {(x, e) : x ∈ V (G), e ∈ E(G), x incidente ad e} .

Se si contano le coppie di A a partire dal primo elemento di ciascuna coppia, si considera A come l’unione (disgiunta)

A = ⋃_{x∈V (G)} {(x, e) : e ∈ E(G), e incidente ad x} ,

implicando

|A| = ∑_{x∈V (G)} |Γ(x)| = ∑_{x∈V (G)} d_{G}(x);

Analogamente, contando le coppie di A a partire dal secondo elemento di ciascuna coppia, si considera A come l’unione (disgiunta)

A = ⋃_{e∈E(G)} {(x, e) : x ∈ V (G), x incidente ad e} ,

e quindi

|A| = ∑_{e∈E(G)} |{x : x vertice di e}| = ∑_{e∈E(G)} 2 = 2|E(G)|.

□

Corollario 1.2 Il numero di vertici di grado dispari è pari.

Dimostrazione. (Prima versione) Dal membro destro di (1.2) si deduce che la somma totale dei gradi è pari: poiché la somma dei gradi pari è necessariamente pari, allora per differenza anche la somma dei gradi dispari è pari; questo significa che il numero dei termini di quest’ultima deve essere pari.

(Seconda versione) Si può operare per induzione sul numero di archi. Passo base: quando |E(G)| = 0, tutti i vertici hanno grado 0 quindi vi sono 0 vertici di grado dispari. Passo induttivo: consideriamo un grafo G in cui E(G) ≠ ∅ (ci sono quindi almeno due vertici). Sia {x, y} ∈ E(G) e costruiamo il grafo G′ in cui V (G′) = V (G) ed E(G′) = E(G) \ {{x, y}}. In G′ vale l’ipotesi induttiva. Osserviamo che d_{G}(x) = d_{G′}(x) + 1, d_{G}(y) = d_{G′}(y) + 1, mentre per gli altri vertici si ha d_{G}(z) = d_{G′}(z). Perciò se x e y hanno la stessa parità di grado in G′, hanno la stessa parità anche in G, dunque il numero di vertici di grado pari o dispari cresce o decresce di 2; se hanno parità diversa, un vertice di grado dispari in G diventa pari in G′ e viceversa, lasciando immutato il numero di vertici di grado dispari. _{□}

1.2 Connessione, distanza

Sia G un grafo e x, y ∈ V (G): una passeggiata in G da x a y è una sequenza

x_{1}, e_{1}, x_{2}, e_{2}, …, x_{t}, e_{t}, x_{t+1}

in cui si alternano vertici e archi del grafo con x_{i} ∈ V (G), e_{i} ∈ E(G), x = x_{1}, y = x_{t+1} e tale che per i = 1, …, t si abbia {x_{i}, x_{i+1}} = e_{i}. La lunghezza della passeggiata è t, ovvero il numero dei suoi archi (con eventuali ripetizioni). Un cammino da x a y è una passeggiata da x a y in cui non ci siano ripetizioni di archi: se i ≠ j allora e_{i} ≠ e_{j}. Un cammino in cui primo e ultimo vertice coincidono si chiama circuito. Un cammino semplice è un cammino in cui non ci siano ripetizioni di vertici: se i ≠ j allora x_{i} ≠ x_{j}, ad eccezione al più di 1 e t + 1; nel caso in cui x_{1} = x_{t+1} il cammino semplice si chiama ciclo. Si dice che x è raggiungibile da y se y = x oppure se esiste una passeggiata da x a y. La relazione di raggiungibilità tra vertici ha la proprietà riflessiva per definizione perché x è raggiungibile da x. La relazione è simmetrica perché se x_{1}, e_{1}, x_{2}, e_{2}, …, x_{t}, e_{t}, x_{t+1} è una passeggiata da x a y, allora x_{t+1}, e_{t}, x_{t}, …, x_{2}, e_{1}, x_{1} è una passeggiata da y ad x. Inoltre la relazione di raggiungibilità è anche transitiva: se c’è una passeggiata da x a y e una passeggiata da y a z, allora z è raggiungibile da x attraverso la passeggiata che si ottiene incollando le precedenti passeggiate in y. Si tratta perciò di una relazione di equivalenza: le classi di questa relazione di equivalenza determinano una partizione dei vertici. Tutti i vertici di una stessa classe sono raggiungibili da ogni altro vertice di questa classe. Un grafo in cui la partizione in questione ha una sola classe si chiama connesso. Se il grafo non è connesso, ogni classe della partizione induce un sottografo chiamato componente connessa. Denoteremo in seguito con λ(G) il numero di componenti connesse di un grafo G.

Proposizione 1.3 Se in G esiste una passeggiata da x a y allora esiste un cammino semplice da x a y.

Dimostrazione. Se nella passeggiata x = x_{1}, e_{1}, x_{2}, e_{2}, …, x_{t}, e_{t}, x_{t+1} = y esistono indici i ≠ j tali che x_{i} = x_{j} = z, allora sia i′ il più piccolo indice per cui z = x_{i′}, e sia j′ l’indice più grande per cui z = x_{j′}. Sostituendo la sezione della passeggiata x_{i′}, e_{i′}, x_{i′+1}, …, x_{j′} con il solo vertice z si ottiene una nuova passeggiata, visto che in questa nuova sequenza ogni arco presente ha gli stessi vicini di prima. D’altronde in questa passeggiata il vertice z non è più ripetuto. Iterando questa procedura con gli altri vertici ripetuti presenti, si arriva ad un cammino semplice. _{□}

Vogliamo ora introdurre una nozione di distanza tra i vertici di un grafo. Sia

d_{G} : V (G) × V (G) → ℝ

la funzione così definita per ogni x, y ∈ V (G):

• se x e y non sono nella stessa componente connessa, poniamo d_{G}(x, y) := +∞;

• se x e y sono nella stessa componente connessa, allora

d_{G}(x, y) := min\{l(\underline{c}) : \underline{c} cammino tra x e y\}  (1.3)

ove l(\underline{c}) denota la la lunghezza del cammino \underline{c}: la distanza tra due vertici è quindi il numero di archi di un cammino di lunghezza minima.

Si noti che la nozione di distanza dipende dal particolare grafo in esame. Vediamo ad esempio che nel grafo G in figura si ha:

[figure: G; •; 3; •; 4; •; 1; •; 2; •; 5; •; 6; d_{G}(1, 6) = +∞; d_{G}(3, 5) = 3; d_{G}(1, 2) = 1]

mentre per il sottografo H ⊂ G si ha:

[figure: H; •; 3; •; 4; •; 1; •; 2; •; 5; •; 6; d_{H}(3, 5) = 4.]

Osserviamo che un cammino che sia il più breve tra x e y necessariamente deve essere semplice, come risulta dalla Proposizione1.3.

Proposizione 1.4 La funzione d_{G} definita in (1.3) è una distanza nel senso usuale degli spazi metrici, ovvero soddisfa le seguenti proprietà per ogni x, y, z ∈ V (G):

1. d_{G}(x, y) ≥ 0 e d_{G}(x, y) = 0 ⇔ x = y.

2. d_{G}(x, y) = d_{G}(y, x).

3. d_{G}(x, y) ≤ d_{G}(x, z) + d_{G}(z, y) (disuguaglianza triangolare).

Dimostrazione. (2.) Basta notare che ogni cammino semplice da x a y percorso "a ritroso" è un cammino (semplice) tra y ed x. (3.) La concatenazione di due cammini di lunghezza minima d_{G}(x, z) e d_{G}(z, y) produce una passeggiata da x a y di lunghezza d_{G}(x, z) + d_{G}(z, y). Quindi la minima lunghezza di un cammino da x a y non può superare questo valore. _{□}

1.3 Circuiti euleriani

In un grafo connesso un circuito euleriano è un circuito (cammino chiuso) che attraversa tutti gli archi. Il seguente teorema, di Euler, fornisce una caratterizzazione dei grafi euleriani, cioè dei grafi che ammettono un circuito euleriano.

Teorema 1.5 Un grafo senza punti isolati ha un circuito euleriano se e solo se è connesso e ogni suo vertice è di grado pari.

Dimostrazione. (⇒) Se nel grafo G senza punti isolati esiste un circuito euleriano, allora il grafo è sicuramente connesso perché altrimenti il circuito euleriano non potrebbe contenere archi appartenenti a diverse componenti connesse. Se percorriamo un circuito euleriano C di G partendo da un suo vertice x, allora ogni volta che attraversiamo un vertice y ≠ x lungo il circuito, escludiamo una coppia di archi dall’insieme degli archi incidenti a y e ancora da percorrere, uno per entrare e uno per uscire. Queste coppie disgiunte quindi esauriscono tutti gli archi incidenti a y, dimostrando che y è di grado pari. Per il vertice x otteniamo un’analoga partizione di tutti i suoi archi in coppie disgiunte se altre alle coppie di archi per ogni singolo attraversamento accoppiamo i due archi della partenza iniziale e ritorno finale in x. In conclusione tutti i vertici hanno grado pari.

Dimostrazione. (⇐) Nel grafo esiste almeno un circuito: infatti partendo da un vertice arbitrario x_{1} ∈ V (G) è possibile costruire un cammino che non si blocca prima di tornare al suo punto iniziale, poiché se si "entra" in un vertice x ≠ x_{1}, se ne può sempre "uscire" passando per un arco non ancora usato, essendo il grado di ogni vertice pari. Consideriamo allora un circuito C massimale (ovvero, non contenuto in un altro circuito del grafo): tale C è euleriano, perché:

• contiene ogni arco incidente ai suoi vertici. Se così non fosse, togliendo gli archi di C dal grafo G, si otterrebbe un grafo G′ in cui ogni vertice è ancora di grado pari: un arbitrario arco incidente a C ma rimasto in G′ potrebbe essere inserito in un circuito non vuoto C′, ma l’unione di C′ e C darebbe un nuovo circuito di G contenente C, contro la massimalità di C;

• per quanto appena detto, la componente connessa di C è il circuito C stesso: poiché G è connesso, si ha G = C, quindi C contiene tutti gli archi di G. (Nota bene: la scrittura "G = C" è un abuso di linguaggio: qui per C si intende il grafo i cui vertici e i cui archi sono quelli che appaiono nella successione vertice–arco–vertice del circuito C.)

□

Possiamo essere più specifici ed affermare che se esiste un circuito euleriano in un grafo, allora da ogni suo vertice è possibile descrivere un circuito euleriano, come enunciato nella seguente:

Proposizione 1.6 Sia G un grafo euleriano. Allora da ogni suo vertice x e per ogni arco e incidente ad x esiste un circuito che parte da x e vi rientra attraverso e.

Dimostrazione. Abbiamo visto in precedenza che in un grafo euleriano ogni vertice ha grado divisibile per 2. Partendo da x, uscendo dall’arco e, è allora possibile tornare in x. Prendiamo tra tutti i circuiti x, e, …, x un circuito massimale C, ovvero un circuito del tipo x, e, …, x che però non sia contenuto propriamente in nessun altro circuito siffatto. Lo stesso ragionamento della Dimostrazione (⇐) del Teorema 1.5, prova che detto circuito massimale è euleriano (comprende tutti gli archi del grafo): allora il circuito ottenuto percorrendo C in ordine inverso, parte da x e vi rientra attraverso e.

□

In un grafo un cammino euleriano è un cammino che comprende tutti gli archi del grafo.

Proposizione 1.7 Sia G un grafo connesso, x, y ∈ V (G): allora esiste un cammino euleriano tra x e y se e solo se x e y sono i soli vertici di grado dispari in G.

Dimostrazione. (⇒) Supponiamo che esista un cammino \underline{c} = x, …, y che parte dal vertice x, termina nel vertice y e attraversa tutti gli archi (una sola volta!). Si possono verificare due casi:

1. {x, y} ∉ E(G): in questo caso, consideriamo il nuovo grafo G′ in cui V (G′) = V (G) ed E(G′) = E(G) ∪ \{\{x, y\}\}. In G′ a partire da \underline{c} possiamo costruire un circuito \underline{c}′ = x, …, y, \{x, y\}, x che quindi percorre (una sola volta!) tutti gli archi di G. Per il Teorema di Eulero 1.5, tutti i vertici avranno grado pari in G′. Ma se z ∈ V (G) si ha

d_{G}(z) = \{ \begin{matrix}d_{G′}(z) & se z ∉ \{x, y\} \\ d_{G′}(z) − 1 & se z ∈ \{x, y\} \end{matrix}

quindi x e y sono i soli vertici di grado dispari in G.

2. {x, y} ∈ E(G): in questo caso non è possibile rimuovere l’arco, come si può vedere dall’esempio in Figura.

[figure: •; 4; •; 3; •; 1; •; 2; x = 1; y = 2; \underline{c} = 1, \{1, 2\}, 2, \{2, 3\}, 3, \{3, 4\}, 4, \{4, 2\}, 2]

Costruiamo invece un grafo G′ aggiungendo un nuovo vertice f e due nuovi archi \{x, f\} e \{f, y\}. In questo grafo si ottiene, dal cammino \underline{c} che contiene tutti gli archi di G, un cammino chiuso \underline{c}′ = x, …, y, \{y, f\}, f, \{f, x\}, x che contiene tutti gli archi di G′, ovvero un cammino euleriano di G′. Per il Teorema 1.5 ogni vertice in G′ ha grado pari, e notando che

d_{G′}(z) = \{ \begin{matrix}2 & se z = f \\ d_{G}(z) + 1 & se z ∈ \{x, y\} \\ d_{G}(z) & se z ∉ \{x, y\} \end{matrix}

segue che x e y sono gli unici vertici di G di grado dispari.

Dimostrazione. (⇐) Come prima si possono presentare due casi:

1. {x, y} ∉ E(G): possiamo allora aggiungere quest’arco al grafo G, ottenendo un grafo G′ in cui tutti i vertici hanno grado pari (abbiamo aumentato di 1 solo il grado di x ed y): per la Proposizione 1.6 esiste un circuito euleriano in G′ che parte da x e rientra in x attraverso l’arco \{x, y\}, sia esso \underline{c}′ = x, …, y, \{y, x\}, x. Chiaramente il cammino \underline{c} = x, …, y che si ottiene da \underline{c}′ cancellando l’arco {x, y}, è euleriano in G.

2. {x, y} ∈ E(G): si costruisce, in modo analogo alla Dimostrazione (⇒), un grafo G′, i cui vertici sono tutti di grado pari. Per la Proposizione 1.6 esiste un circuito euleriano \underline{c}′ in G′ che parta da x e rientri in x attraverso l’arco \{f, x\}, e necessariamente sarà \underline{c}′ = x, …, y, \{y, f\}, f, \{f, x\}, x: allora il cammino \underline{c} = x, … y è euleriano in G.

□

1.4 Connessione e numero di archi

Un grafo G senza cicli viene chiamato foresta; se G oltre ad essere aciclico è anche connesso, parleremo di albero. Le componenti connesse di una foresta sono quindi alberi. Osservazione. Si noti che in un grafo aciclico esiste al più un solo cammino tra due vertici.

Data una famiglia di sottoinsiemi di un insieme, un membro della famiglia è massimale per inclusione (rispettivamente: minimale) se non è propriamente contenuto in (rispettivamente: se non contiene propriamente) un altro membro della famiglia.

Un sottografo H di G è massimale rispetto ad una proprietà P se P è vera in H e se per ogni sottografo F ⊇ H tale che la proprietà P vale su F allora F = H (ovvero H non è contenuto propriamente in nessun sottografo di G che verifica P). Analogamente un sottografo H di un grafo G è minimale rispetto ad una proprietà P se P è vera su H e se per ogni sottografo F ⊆ H tale che la proprietà P vale su F allora F = H (non vi sono sottografi propri di H che verificano P).

Vediamo un esempio. Sia G il grafo indicato in figura.

[figure: G; •; b; •; d; •; c; •; a; •; e; V (G) = {a, b, c, d, e}]

Consideriamo la famiglia di tutti i sottoinsiemi di V (G) il cui sottografo indotto in G è completo:

{{a}, {b}, {c}, {d}, {e}, {a, b}, {a, d}, {b, c}, {b, d}, {c, d}, {d, e}, {a, b, d}, {b, c, d}}

Gli elementi di tale famiglia che inducono un sottografo completo massimale sono {d, e}, {a, b, d}, {b, c, d}. Si noti che pur essendo massimali, tali sottoinsiemi non hanno la stessa cardinalità.

Se |V (G)| = n e |E(G)| = \binom{n}{2} allora si può affermare che G è sicuramente connesso. Lo stesso vale se |E(G)| = \binom{n}{2}−1. È naturale domandarsi qual è il numero massimo D(n) di archi che un grafo sconnesso su n vertici può avere. Si noti che questo significa che se un grafo su n vertici è tale che |E(G)| > D(n) allora G è necessariamente connesso.

Proposizione 1.8

D(n) = \binom{n − 1}{2} = \frac{(n − 1)(n − 2)}{2}.

Dimostrazione. Quando è massimo il numero di archi presenti è minimo il numero degli archi assenti. Se G non è connesso, ciò significa che i suoi vertici sono divisi in due insiemi disgiunti, di cardinalità x e n−x con 1 ≤ x ≤ n−1, e tali che non ci sono in G archi con vertici in ambedue questi insiemi. Il numero di archi che avrebbero potuto collegare i due sottoinsiemi (ma che sono stati tolti) è x(n − x) = −x^{2} + nx. Il minimo per questo polinomio in x di grado 2 si ottiene per x = 1 e x = n−1; quindi il massimo numero possibile di archi presenti è dato dalla componente con n − 1 vertici ed è \binom{n−1}{2}. _{□}

Osservazione. Se G è un grafo connesso come sono fatti i suoi sottografi di copertura connessi minimali (rispetto ad essere connessi e di copertura)? È facile convincersi che se un sottografo ricoprente T ⊆ G è connesso e minimale, allora non ha cicli: altrimenti, il sottografo di T che si otterrebbe eliminando un arco da un ciclo sarebbe ancora connesso, contraddicendo la minimalità di T. Perciò un sottografo di copertura connesso minimale è un albero.

Teorema 1.9 Un grafo G connesso con n vertici è un albero se e solo se |E(G)| = n − 1.

Dimostrazione. (⇒) Sia G un albero: fissato x ∈ V (G), vogliamo descrivere una biiezione f : V (G) \ {x} → E(G). Per ogni y ∈ V (G) \ {x}, sia f(y) ∈ E(G) l’arco iniziale del cammino semplice da y a x: tale cammino esiste ed è unico, essendo G un albero, e questo garantisce il fatto che la definizione della funzione f sia ben posta. Vediamo ora che tale f è iniettiva. Siano y, z ∈ V (G) \ {x}, y ≠ z e supponiamo che f(y) = f(z) = e. Questo implica che e = {y, z} e che tale arco chiude un ciclo in G, contro ipotesi.

x y  z e

Inoltre, ogni arco e = {y, z} è il primo arco di un cammino da uno dei suoi due vertici verso x: sia c(z) il cammino semplice da z ad x in G; se f(z) ≠ e allora (y, e, z, c(z)) è il cammino (unico!) da y ad x e dunque f(y) = e. Tale ragionamento mostra che l’applicazione f è anche suriettiva: ne segue che |V (G) − {x}| = |E(G)| cioè |E(G)| = n − 1. Dimostrazione. (⇐) Per induzione. Caso base: n = 2. Il grafo ha 2 vertici ed un solo arco che li unisce: questo evidentemente è un albero. Passo induttivo: Supponiamo che un grafo su n−1 vertici con n−2 archi sia un albero. Prendiamo in considerazione un grafo G con |V (G)| = n ed |E(G)| = n−1. Essendo G connesso per ipotesi, per ogni suo vertice x ∈ V (G) vale d_{G}(x) ≥ 1. Se per assurdo tutti i vertici avessero grado almeno 2, usando la relazione (1.2), si avrebbe

2n ≤ ∑_{x∈V (G)} d_{G}(x) = 2|E(G)| = 2(n − 1),

impossibile. Esiste allora almeno un vertice, sia y, di grado 1. Sia G′ il grafo ottenuto da G rimuovendo il vertice y e l’unico arco, sia e, ad esso adiacente: ne risulta |V (G′)| = n − 1, |E(G′)| = n − 2. Per induzione G′ è un albero. Poiché l’inserzione di x e di e in G′ non può creare un ciclo, ne segue che anche G è un albero. _{□}

Corollario 1.10 Se |V (G)| = n e |E(G)| < n − 1, allora G non è connesso.

Dimostrazione. Supponiamo per assurdo che G sia connesso. Consideriamo G′ ⊆ G sottografo ricoprente connesso e minimale. Per quanto appena visto si ha che |E(G′)| = n − 1, ma allora sarebbe n − 1 = |E(G′)| ≤ |E(G)| < n − 1: impossibile.

□

Proposizione 1.11 In un albero (con più di un vertice!) ci sono almeno due vertici di grado 1.

Dimostrazione. Sia c il numero di vertici di grado 1 di un grafo G: allora per la sommatoria dei gradi vale

∑_{x∈V (G)} d_{G}(x) = ∑_{{x∈V (G) \atop d_{G}(x)=1}} d_{G}(x) + ∑_{{x∈V (G) \atop d_{G}(x)≥2}} d_{G}(x) ≥ c + 2(n − c).

In particolare, se G è un albero, per il Teorema 1.9 si ha

∑_{x∈V (G)} d_{G}(x) = 2|E(G)| = 2(n − 1) :

confrontando le relazioni precedenti segue c ≥ 2. (Dimostrazione alternativa: gli estremi di un cammino massimale di G sono entrambi di grado 1.) _{□}

Possiamo trovare in un albero più di due vertici di grado 1? Si noti che in un albero T se x ∈ V (T) ha grado d_{T} (x) > 1, allora ci sono almeno d_{T} (x) vertici di grado 1. Si prenda infatti l’insieme di tutti i cammini semplici di T che abbiano un estremo in x e siano massimali: ve ne sono esattamente d_{T} (x), e per ogni tale cammino, l’estremo diverso da x ha grado 1.

[figure: •; x; •; •; •; •; •; •; •; •]

Se ne deduce il seguente

Corollario 1.12 In un albero T se indichiamo con s il numero dei vertici di grado 1 si ha

s ≥ max_{x∈V (T)} d_{T} (x) = d(T).

Ricordiamo che una foresta è un grafo semplice senza cicli e che le componenti connesse di una foresta sono alberi.

Proposizione 1.13 In una foresta F il numero di componenti connesse λ(F) soddisfa la relazione

|E(F)| = |V (F)| − λ(F).  (1.4)

Dimostrazione. Per ogni componente connessa F_{i} di F, per (1.9) si ha |E(F_{i})| = |V (F_{i})| − 1; quindi

|E(F)| = ∑_{i=1}^{λ(F)} |E(F_{i})| = ∑_{i=1}^{λ(F)} |V (F_{i})| − (∑_{i=1}^{λ(F)} 1) = |V (F)| − λ(F).

□

Il seguente Teorema, dovuto ad A. Bondy, è legato alla compressione di dati.

Teorema 1.14 Dati n sottoinsiemi distinti A_{i} di un insieme X di n elementi, allora esiste x ∈ X tale che gli insiemi A_{i} \ {x} siano ancora tutti distinti.

Dimostrazione. Si può considerare senza perdita di generalità X = {1, 2, … n} e associare ad ogni sottoinsieme A_{i} il suo vettore caratteristico \underline{x}^{A_{i}} = (x_{1}^{A_{i}} … x_{n}^{A_{i}}). (Ricordiamo che, fissato un sottoinsieme A ⊆ [n], il suo vettore caratteristico \underline{x}^{A} = (x_{1}^{A} … x_{n}^{A}) è dato da x_{j}^{A} = 1 se j ∈ A, x_{j}^{A} = 0 se j ∉ A). Ad esempio, se n = 6 al sottoinsieme A = {2, 3, 5, 6} ⊆ [6] associamo la stringa binaria \underline{x}^{A} = (0, 1, 1, 0, 1, 1) ∈ \{0, 1\}^{6}.

Il problema diventa: prese n stringhe distinte lunghe n trovare un indice j tale che le n stringhe lunghe n − 1 ottenute sopprimendo la j-sima coordinata restino distinte.

Consideriamo il grafo G i cui vertici siano V (G) = \{\underline{x}^{A_{i}} : 1 ≤ i ≤ n\} e tra due stringhe esiste un arco se le stringhe differiscono per una sola coordinata. "Coloriamo" gli archi del grafo con gli indici delle coordinate: associamo il colore i all’arco \{A, B\} ∈ E(G) se i è l’indice dell’unica coordinata in cui le stringhe \underline{x}^{A} e \underline{x}^{B} differiscono. Dimostriamo ora che in questa colorazione non possono essere presenti tutti i colori {1, 2, … n}: uno tra i colori non utilizzati potrà allora essere eliminato. Per fare questo, affermiamo che in un ciclo arbitrario di G ogni etichetta presente su un arco appare almeno due volte: infatti percorrendo il ciclo a partire da un suo qualunque vertice, alla fine del giro tutte le differenze tra coordinate si sono annullate. Perciò togliendo un arco (colorato) da un ciclo, il numero di archi nel nuovo grafo così ottenuto diminuisce, ma non diminuisce il numero dei colori presenti sugli archi. Iterando questo procedimento distruggiamo tutti i cicli mantenendo inalterato il numero di colori. Al termine di questo processo otteniamo un grafo aciclico: dato che gli archi di una foresta sono al massimo n − 1, non potremmo averli colorati con n colori distinti! _{□}

1.5 Algoritmo di Kruskal

Sia G un grafo semplice. Chiamiamo funzione di costo una funzione

c : E(G) → R^{+}

che associa ad ogni arco del grafo un numero reale non negativo. Il costo di un sottografo F di G è il numero reale c(F) definito come

c(F) = ∑_{e∈E(F)} c(e).

Ha senso allora cercare gli alberi ricoprenti di costo minimo. Quello che viene descritto di seguito è un algoritmo, introdotto da J.B.Kruskal in [5], che fornisce un albero di copertura di costo minimo.

Sia G un grafo connesso su n vertici con funzione di costo c assegnata. L’algoritmo costruisce ad ogni passo una foresta sui vertici di G, aggiungendo un nuovo arco alla foresta già costruita.

• Passo iniziale: si inserisce nella foresta F_{0} = (V (G), ∅) un arco a scelta tra quelli di E(G) che hanno costo minimo: sia esso e_{1} (quindi c(e_{1}) = min_{e∈E(G)} c(e)).

• Passo t-simo: abbiamo costruito una foresta F_{t−1} = (V (G), E(F_{t−1})) con t − 1 archi E(F_{t−1}) = {e_{1}, e_{2}, …, e_{t−1}}. Inseriamo ora un nuovo arco, sia e_{t} ∈ E(G) \ E(F_{t−1}) in modo che

1. per il sottografo F_{t} = (V (G), E(F_{t})) di archi

E(F_{t}) = {e_{1}, e_{2}, …, e_{t−1}, e_{t}}

valga λ(F_{t}) < λ(F_{t−1}); 2. il costo di e_{t} sia minimo tra gli archi di E(G) non ancora inseriti per i quali

valga la condizione precedente, i.e.

c(e_{t}) = min{c(e) : e ∉ E(F_{t−1}), λ(e_{1}, …, e_{t−1}, e) < λ(e_{1}, …, e_{t−1})}

ove con λ(e_{1}, …, e_{j}) si indica il numero di componenti connesse della foresta (V (G), {e_{1}, …, e_{j}}).

• ci fermiamo dopo il passo t = n − 1 (cioè non appena sono stati inseriti n − 1 archi)

Teorema 1.15 Ogni sottografo di G ottenuto tramite l’algoritmo di Kruskal è un albero ricoprente di costo minimo.

Dimostrazione. Anzitutto si noti che il sottografo F_{n−1} di G è un albero. Ad ogni passo dell’algoritmo infatti, la condizione 1. ci assicura che ogni sottografo F_{t} di G è una foresta, poiché vale la relazione λ(F_{t}) + t = n della Proposizione1.13: allora F_{n−1}, essendo una foresta con esattamente n − 1 archi, è un albero.

Siano e_{1}, …, e_{n−1} gli archi utilizzati (in quest’ordine) dall’algoritmo: per costruzione si ha che c(e_{1}) ≤ c(e_{2}) ≤ … ≤ c(e_{n−1}). Sia ora T un altro albero ricoprente di G ed ordiniamo l’insieme dei suoi archi E(T) = {a_{1}, … a_{n−1}} per costo crescente, i.e. c(a_{1}) ≤ c(a_{2}) ≤ … ≤ c(a_{n−1}). Affermiamo che c(e_{i}) ≤ c(a_{i}) per i = 1, …, n − 1 (questo implica che c(F_{n−1}) ≤ c(T) per ogni albero ricoprente T di G, ovvero che F_{n−1} ha costo minimo). Durante l’esecuzione dell’algoritmo il numero delle componenti connesse dei sottografi che via via vengono costruiti diminuisce strettamente passando da n fino a 1. Supponiamo per assurdo che esista almeno un indice s per cui c(e_{s}) > c(a_{s}), e sia esso il minimo: quindi vale c(e_{s}) > c(a_{s}) ≥ c(a_{s−1}) ≥ … ≥ c(a_{1}). Se al passo s-esimo abbiamo scelto l’arco e_{s} anziché uno fra gli archi {a_{1}, …, a_{s}}, allora deve aversi

λ(e_{1}, …, e_{s−1}, a_{1}, …, a_{s}) = λ(e_{1}, …, e_{s−1})  (1.5)

(l’inserzione dell’arco a_{s} non avrebbe diminuito il numero di componenti connesse). Da questa uguaglianza, ricordando che aggiungendo archi il numero di componenti connesse non può aumentare, si ricava

λ(a_{1}, …, a_{s}) ≥ λ(e_{1}, …, e_{s−1}, a_{1}, …, a_{s}).  (1.6)

Confrontando la disequazione (1.6) con l’uguaglianza (1.5) si arriva a

λ(a_{1}, …, a_{s}) ≥ λ(e_{1}, …, e_{s−1}).  (1.7)

Ma le due foreste in questione soddisfano (cfr. (1.4))

λ(a_{1}, …, a_{s}) + s = n = λ(e_{1}, …, e_{s−1}) + s − 1  (1.8)

implicando

λ(a_{1}, …, a_{s}) < λ(e_{1}, …, e_{s−1}),  (1.9)

una contraddizione con (1.7). _{□}

Alberi, foreste e permutazioni

2.1 Formula di Cayley

È interessante stabilire, fissato un grafo G, quanti sono gli alberi di ricoprimento di G. Il problema non è di facile soluzione, in generale. In particolare, dato un intero n, potremmo cercare di contare quanti alberi di copertura distinti occorrono nel grafo completo su n vertici K_{n}. Denotiamo in seguito con T (n) tale quantità. Partiamo da un esempio. Sia n = 3.

[figure: •; 1; •; 2; •; 3; K_{3}]

I suoi alberi di copertura sono i seguenti:

[figure: •; 1; •; 2; •; 3; •; 1; •; 2; •; 3; •; 1; •; 2; •; 3]

Se non si tenesse conto delle etichette, i tre alberi sarebbero indistinguibili; in effetti sono tutti isomorfi al cammino semplice su 3 vertici:

•  •  •

Facciamo ancora un esempio, con n = 4.

[figure: •; 4; •; 3; •; 1; •; 2; K_{4}]

Ecco due tra gli alberi di copertura di K_{4} isomorfi ad un cammino semplice su 4 vertici:

[figure: •; 4; •; 3; •; 1; •; 2; oppure; •; 4; •; 3; •; 1; •; 2]

È interessante notare che vi sono alberi di copertura di K_{4} che non sono isomorfi a cammini semplici, ad esempio:

[figure: •; 4; •; 3; •; 1; •; 2]

Il lettore può verificare che ci sono 4 alberi di ricoprimento di K_{4} isomorfi all’albero della figura precedente.

Il seguente notevole risultato, noto come formula di Cayley, dà una formula chiusa per l’enumerazione degli alberi di copertura di K_{n}.

Teorema 2.1 Per n ≥ 1, il numero T (n) di alberi etichettati distinti su n vertici è

T (n) = n^{n−2}.

Nonostante T (n) si esprima in modo così semplice, non esistono dimostrazioni altrettanto semplici e dirette di questo fatto. Nel corso degli anni sono state trovate numerose dimostrazioni della formula di Cayley. Le idee basilari delle varie dimostrazioni differiscono tra loro in modo sostanziale; mettendole insieme si scoprono legami talvolta insospettati tra le varie parti della matematica. Ad illustrazione di ciò, daremo tre diverse dimostrazioni della formula. Per altre dimostrazioni si consultino i testi [8], [10], [14], in bibliografia.

2.2 Il codice di Prüfer

Descriveremo ora una codifica degli alberi su n vertici, etichettati in [n], tramite parole sull’alfabeto {1, 2, …, n} di lunghezza n − 2, nota appunto come codice di Prüfer (cfr. [11]).

Associamo al generico albero T di copertura di K_{n} la stringa n-aria

f_{n}(T) = (a_{1}, a_{2}, …, a_{n−2}) ∈ [n]^{n−2}

nel seguente modo iterativo:

• Primo passo. Consideriamo tra i vertici di grado 1 di T_{0} = T quello di etichetta minima, sia esso b_{1}: esiste un unico vertice y adiacente a b_{1} (poiché b_{1} è di grado 1), chiamiamo allora a_{1} := y. Cancelliamo da T il vertice b_{1} e l’arco {a_{1}, b_{1}} ad esso adiacente: otterremo ancora un albero T_{1} sugli n − 1 vertici rimanenti.

• i-simo passo. Abbiamo cancellato i − 1 vertici da T. Consideriamo, nell’albero T_{i−1} su (n−i+1) vertici, il suo vertice di grado 1 di etichetta minima, sia esso b_{i}. Vi è un unico vertice y′ ad esso adiacente, poniamo allora a_{i} = y′. Cancelliamo da T_{i−1} il vertice b_{i} e l’arco {a_{i}, b_{i}}: ciò che rimane è un albero T_{i} su n − i vertici.

• Ci fermiamo quando l’albero così “potato” ha un solo arco (e due vertici), ovvero dopo n − 2 passi.

Illustriamo l’algoritmo con un esempio. Il vertice cerchiato ad ogni passo è quello di grado 1 di etichetta minima e verrà rimosso.

[figure: T_{0} = T; •; 8; •; 6; •; 2; •; 3; •; 4; •; 7; •; 1; •; 5; T_{1}; •; 8; •; 6; •; 3; •; 4; •; 7; •; 1; •; 5]

a_{1} = 6 b_{1} = 2  a_{2} = 4 b_{2} = 3

[figure: T_{2}; •; 8; •; 6; •; 4; •; 7; •; 1; •; 5; T_{3}; •; 8; •; 6; •; 4; •; 7; •; 1]

a_{3} = 1 b_{3} = 5  a_{4} = 4 b_{4} = 1

[figure: T_{4}; •; 8; •; 6; •; 4; •; 7; T_{5}; •; 8; •; 6; •; 4; T_{6}; •; 8; •; 6]

a_{5} = 4 b_{5} = 7  a_{6} = 6 b_{6} = 4

Si ottiene f_{8}(T) = (6, 4, 1, 4, 4, 6). Ricordando che |[n]^{n−2}| = n^{n−2}, possiamo enunciare il Teorema di Cayley nella seguente forma:

Teorema 2.2 Sia T_{n} l’insieme degli alberi di copertura di K_{n}. Il codice di Prüfer f_{n} : T_{n} → [n]^{n−2} è una biiezione.

Dimostrazione. Anzitutto notiamo che gli interi b_{i}, i = 1, …, n − 2, sono tutti distinti, mentre i vertici a_{i} possono anche ripetersi. Inoltre quando l’algoritmo si arresta abbiamo un solo arco residuo, e certamente uno dei suoi due vertici deve essere n: infatti n "sopravvive" perché, anche qualora a un certo passo dell’algoritmo il vertice etichettato da n diventasse di grado 1, in ogni caso ci sarebbe almeno un altro vertice di grado 1, e la sua etichetta necessariamente deve essere minore di n. Per comodità poniamo a_{n−1} = n e sia b_{n−1} l’unico elemento dell’insieme [n − 1] \ {b_{1}, …, b_{n−2}}. Si può allora rappresentare il processo di codifica con una matrice 2 × (n − 1) (quello che chiameremo il codice completo):

( \begin{matrix}a_{1} & a_{2} & … & a_{n−2} & a_{n−1} \\ b_{1} & b_{2} & … & b_{n−2} & b_{n−1} \end{matrix} )

dove b_{1}, …, b_{n−2} sono i vertici che vengono "potati" di volta in volta nella costruzione,

a_{1}, …, a_{n−2} sono i loro rispettivi adiacenti, la colonna ( \begin{matrix}a_{i} \\ b_{i} \end{matrix} ) rappresenta un arco

dell’albero T e le colonne seguono l’ordine in cui gli archi sono stati tolti dall’albero. Il codice di Prüfer è rappresentato dalla stringa f_{n}(T) = (a_{1}, …, a_{n−2}) (la (n − 1)– sima colonna non viene usata in quanto è determinata univocamente dalle condizioni a_{n−1} = n e {b_{1}, …, b_{n−2}} ∪ {n, b_{n−1}} = [n]). Abbiamo visto che per l’albero T dell’esempio precedente il codice di Prüfer è f_{8}(T) = (6, 4, 1, 4, 4, 6), mentre il suo codice completo è

( \begin{matrix}6 & 4 & 1 & 4 & 4 & 6 & 8 \\ 2 & 3 & 5 & 1 & 7 & 4 & 6 \end{matrix} ) .

Alberi di copertura diversi hanno codice completo diverso, poiché l’insieme degli archi dell’albero T è determinato dal suo codice completo:

E(T) = {{a_{i}, b_{i}} : i = 1, 2, …, n − 1}.

Vediamo allora come dal codice di Prüfer di T sia possibile ricostruire il codice completo (la matrice a 2 righe ed n − 1 colonne). Per costruzione, i vertici di T di grado maggiore di 1 hanno etichette nell’insieme {a_{1}, a_{2}, …, a_{n−2}}. Inoltre b_{1} ≠ n, quindi

b_{1} = min {[n] − {a_{1}, …, a_{n−2}, n}} .

Ricordando che, nel momento in cui si rimuove un vertice, esso ha etichetta minima tra quelli di grado 1 e non può essere nessuno dei precedenti, si ottiene anche

b_{2} = min {[n] \ {a_{2}, … a_{n−2}, n, b_{1}}}
…
b_{i} = min {[n] \ {a_{i}, a_{i+1}, … a_{n−2}, n, b_{1} … b_{i−1}}}
…
b_{n−1} = min {[n] \ {n, b_{1} … b_{n−2}}}

Questo mostra che l’applicazione f_{n} è iniettiva. Proviamo ora che f_{n} è anche suriettiva. Partendo da una stringa (a_{1}, a_{2}, …, a_{n−2}) ∈ [n]^{n−2} abbiamo appena visto che tramite le relazioni precedenti si può costruire univocamente una matrice 2 × (n − 1):

( \begin{matrix}a_{1} & a_{2} & … & a_{n−2} & a_{n−1} \\ b_{1} & b_{2} & … & b_{n−2} & b_{n−1} \end{matrix} ) .

Sia G il grafo di vertici V (G) = [n] ed archi indotti dalle colonne della matrice, ovvero E(G) = {{a_{i}, b_{i}} : i = 1, 2, …, n − 1}. Vogliamo provare che il grafo così ottenuto G è aciclico: questo sarà sufficiente a dimostrare che G è un albero, essendo aciclico con esattamente n − 1 archi ed n vertici. Per costruzione gli elementi b_{i} della seconda riga sono tutti distinti. Inoltre b_{i} non è un’estremità di nessuno degli archi {a_{i+1}, b_{i+1}}, …, {a_{n−1}, b_{n−1}}, quindi {a_{i}, b_{i}} non può chiudere un ciclo nel grafo con vertici in [n] ed archi {a_{i+1}, b_{i+1}}, …, {a_{n−1}, b_{n−1}}. L’applicazione f_{n} è pertanto biiettiva e ne segue T (n) = n^{n−2}. _{□}

Si invita a questo punto il lettore a costruire l’albero associato ad una stringa di sua scelta. Osservazione. Sia f_{n}(T) = (a_{1}, …, a_{n−2}) il codice di Prüfer di un fissato albero T su [n] vertici: se denotiamo con δ(l) = |{i : a_{i} = l}| il numero di occorrenze di un intero l ∈ [n] nella stringa f_{n}(T), allora d_{T} (l) = δ(l) + 1. Infatti se a_{i} = l allora al passo i–simo dell’algoritmo abbiamo potato un vertice v ∈ Γ_{T} (l) che era di grado 1 nell’albero T_{i−1}, ed il minimo con questa proprietà tra i vertici di T_{i−1}: pertanto si ha d_{T_{i−1}}(l) = d_{T_{i}}(l) + 1 se e solo se a_{i} = l.

2.3 Vertebrati e formula di Cayley

Si noti che la nozione di grafo aciclico connesso (ovvero: albero!) è diversa da quella di albero radicato (rooted tree) che si incontra più frequentemente in informatica.

Fissato un albero T su [n] vertici, possiamo costruire un albero con radice “puntando” uno specifico vertice. In altre parole, un albero radicato è una coppia (T, r), con r ∈ V (T). Si deduce che, per ogni fissato albero su n vertici, vi sono n alberi radicati distinti, e quindi il numero RT (n) di alberi radicati su n vertici è pari a n volte il numero totale di alberi etichettati:

RT (n) = nT (n).

Nella figura seguente, a sinistra abbiamo un albero su 8 vertici, a destra abbiamo l’albero radicato che si ottiene con la scelta del vertice 1 come radice.

[figure: T; •; 8; •; 6; •; 2; •; 3; •; 4; •; 7; •; 1; •; 5; RT; •; 8; •; 6; •; 2; •; 3; •; 4; •; 7; •; 1; •; 5]

Spesso si usa rappresentare un albero radicato nel seguente modo (“pettinandolo” dalla radice verticalmente, oppure orizzontalmente)

[figure: •; 1; •; 4; •; 5; •; 6; •; 3; •; 7; •; 8; •; 2]

Chiameremo vertebrato ogni albero etichettato su n vertici in cui si scelgano 2 vertici speciali (non necessariamente distinti) detti testa e coda. Un vertebrato può essere rappresentato perciò da una terna (T, c, t), dove T è un albero di copertura di K_{n} e c, t ∈ [n]. Fissato un albero di copertura T, si possono ottenere da esso n^{2} vertebrati distinti. Pertanto se indichiamo con V_{n} la famiglia dei vertebrati su n vertici si ha

|V_{n}| = n^{2}T (n).  (2.1)

Se T è l’albero non radicato della figura precedente, qui sotto a sinistra si trova il vertebrato (T, c, t) con c = 7, t = 1.

[figure: •; 8; •; 6; •; 2; •; 3; •; 4; •; 7; •; 1; •; 5; •; 7; •; 4; •; 6; •; 3; •; 2; •; 8; •; 1; •; 5; •; 7; ⟶; •; 4; ⟶; •; 6; •; 3; •; 2; •; 8; •; 1; •; 5]

Un vertebrato (T, c, t) determina univocamente un cammino C = c, …, t (l’unico!) che unisce c a t in T. Se si eliminano da T gli archi del cammino C, si ottiene una foresta. Ognuna delle componenti connesse della foresta contiene uno e un solo vertice di C e può essere pensata come un albero radicato in quel vertice di C. Indichiamo con V (C) l’insieme dei vertici che appaiono nel cammino C. Dato un vertebrato (T, c, t) restano perciò specificati un cammino orientato C = c, …, t e una famiglia {T_{y}}_{y∈V (C)} di alberi radicati (T_{y}, y), eventualmente ridotti al solo punto y, a due a due disgiunti (vedi figura precedente). Viceversa fissiamo un sottoinsieme C ⊆ [n] con la scelta di un un ordinamento lineare su C, denotato qui con < (che può essere pensato come un cammino orientato sugli elementi di C), e sia assegnata una famiglia di alberi {T_{x}}_{x∈C} dove ogni T_{x} è un albero radicato in x, con le proprietà seguenti:

• (V (T_{x}) \ {x}) ∩ C = ∅;

• V (T_{x}) ∩ V (T_{y}) = ∅ per ogni x ≠ y;

• ∪_{x∈C}V (T_{x}) = [n].

Allora dalla terna (C, <, {T_{x}}_{x∈C}) si può costruire il vertebrato (T, c, t), ove se

v_{1} < v_{2} < … < v_{h}

sono gli elementi di C nell’ordinamento lineare prescelto, allora c = v_{1}, t = v_{h} e T = (V (T), E(T)), con V (T) = [n],

E(T) = ⋃_{x∈C} E(T_{x}) ∪ {{v_{1}, v_{2}}, {v_{2}, v_{3}}, …, {v_{h−1}, v_{h}}}.

Chiamiamo endofunzione di A una funzione di un insieme A in sé. Ci proponiamo adesso di descrivere una biiezione tra i vertebrati su n vertici e le endofunzioni di un insieme ad n elementi, che possiamo pensare come l’insieme [n]. Poniamo

F_{n} = {f : [n] → [n]}

Teorema 2.3 (A. Joyal) Per ogni intero n ≥ 0 esiste una biiezione tra endofunzioni di [n] e vertebrati su n vertici e quindi si ha

|F_{n}| = |V_{n}|.  (2.2)

Prima di vederne la dimostrazione, vediamo come dal Teorema precedente segue il Teorema di Cayley:

Corollario 2.4 Per ogni intero n ≥ 0 si ha

T (n) = n^{n−2}.

Dimostrazione. Una endofunzione f ∈ F_{n} è completamente determinata quando sono specificate le immagini secondo f di ogni intero i ∈ [n]. Ci sono n modi diversi di assegnare un valore ad f(1), n modi diversi di assegnare un valore ad f(2), etc. Infatti se j ≠ i la scelta di un valore per f(j) non vincola la scelta di un valore per f(i) (la funzione non deve necessariamente essere iniettiva, suriettiva o altro): in totale vi sono n · n · . . . · n = n^{n} modi distinti di descrivere un’endofunzione, quindi |F_{n}| = n^{n}. Segue dalla (2.2), ricordando la relazione (2.1), che

T (n) = n^{n}/n^{2} = n^{n−2}.
□

Vediamo ora alcune proprietà di un’endofunzione. Un elemento a ∈ [n] si dice ricorrente rispetto ad una endofunzione f ∈ F_{n} se esiste un intero t > 0 tale che f^{t}(a) = a; chiameremo un elemento transiente se non è ricorrente. Denotiamo con R_{f} ⊆ [n] l’insieme degli elementi ricorrenti per la funzione f. Possiamo quindi ripartire [n] in ricorrenti e transienti: [n] = R_{f} ∪ ([n] \ R_{f}). Denotiamo come di consueto con f|_{R_{f}} la restrizione di f all’insieme dei ricorrenti R_{f}.

Proposizione 2.5 La funzione f|_{R_{f}} è una biiezione dell’insieme dei ricorrenti:

f|_{R_{f}} : R_{f} ↔ R_{f}.

Dimostrazione.

1. Verifichiamo che f|_{R_{f}} mappa R_{f} in sé, cioè vale f(R_{f}) ⊆ R_{f}. Sia a un elemento ricorrente per f: esiste quindi un intero strettamente positivo s per il quale f^{s}(a) = a. Allora f^{s}(f(a)) = f(f^{s}(a)) = f(a), quindi anche f(a) è ricorrente.

2. Iniettività di f|_{R_{f}}. Siano a, b ∈ R_{f} con a ≠ b: esistono allora interi positivi t, s > 0 tali che f^{s}(a) = a e f^{t}(b) = b: si noti che iterando la f vale anche f^{ks}(a) = a e f^{kt}(b) = b, per ogni intero positivo k. Supponiamo per assurdo che f(a) = f(b). Allora, applicando f ad entrambi i membri di questa uguaglianza, per ogni intero m ≥ 1 si deve anche avere f^{m}(a) = f^{m}(b). Ne seguirebbe in particolare:

a = f^{s}(a) = f^{ts}(a) = f^{ts}(b) = f^{st}(b) = f^{t}(b) = b,

contro l’assunzione a ≠ b.

Ricordiamo che se una funzione g : A → B è iniettiva e l’insieme A è finito, allora |g(A)| = |A|. In questo caso quindi dalla relazione |f(R_{f})| = |R_{f}| del punto 2. e dalla relazione f(R_{f}) ⊆ R_{f} del punto 1. si deduce che f(R_{f}) = R_{f}, ovvero f è biunivoca su R_{f}. _{□} Proposizione 2.6 Per ogni transiente a ∈ [n] \ R_{f} esiste un intero positivo k tale che f^{k}(a) ∈ R_{f}.

Dimostrazione. La sequenza (a, f(a), f^{2}(a), …, f^{j}(a), …) delle immagini successive di a tramite la funzione f ha i suoi elementi nell’insieme finito [n]: esistono quindi i, j con i < j tali che f^{i}(a) = f^{j}(a). Allora f^{j−i}(f^{i}(a)) = f^{j−i+i}(a) = f^{j}(a) = f^{i}(a), quindi essendo j − i > 0 segue f^{i}(a) ∈ R_{f}. _{□}

In altre parole, applicando f ad un transiente si arriva prima o poi ad un ricorrente: chiamiamo punto di contatto di un transiente a ∉ R_{f} il primo elemento della lista a, f(a), f^{2}(a) … che appartiene ad R_{f}: se s = min{j : f^{j}(a) ∈ R_{f}}, allora f^{s}(a) è il punto di contatto del transiente a ai ricorrenti di f. Avere lo stesso punto di contatto è una relazione di equivalenza fra i transienti (banale verifica!): le classe di equivalenza di questa relazione sono quindi indicizzate dagli elementi ricorrenti. Pertanto, se poniamo per ogni x ∈ R_{f}

V (T_{x}) = {a ∉ R_{f} : il punto di contatto di a è x} ∪ {x} ⊆ [n]

tali insiemi sono a due a due disgiunti:

V (T_{x}) ∩ V (T_{y}) = ∅ se x ≠ y

e anche

⋃_{x∈R_{f}} V (T_{x}) = [n].

Si noti che l’insieme V (T_{x}) può ridursi al solo elemento x.

A questo punto vogliamo visualizzare le funzioni in termini di grafi, e per questo abbiamo bisogno di un nuovo concetto di grafo, in cui gli archi hanno un’orientazione.

Un grafo diretto G è una coppia di insiemi (V (G), E(G)) dove V (G) è un insieme finito, E(G) ⊆ V (G) × V (G) è un insieme di coppie ordinate di punti di V (G). Possiamo dare una rappresentazione grafica di un grafo diretto come per i grafi semplici, unendo però un vertice a ad un vertice b con un arco orientato verso b se e solo se la coppia (a, b) ∈ E(G). In figura abbiamo rappresentato il grafo diretto in cui V (G) = {1, 2, 3} ed E(G) = {(1, 2), (3, 1), (3, 2)}.

1  3  2

In un grafo diretto G si definisce il grado entrante di un vertice x ∈ V (G) come il numero di archi di G per i quali x è il vertice di "arrivo":

d_{G}^{+}(x) = |{a : (a, x) ∈ E(G)}|;  (2.3)

analogamente il grado uscente è il numero di archi di G per i quali x è il vertice di partenza:

d_{G}^{−}(x) = |{a : (x, a) ∈ E(G)}|.  (2.4)

Nell’esempio della figura precedente si ha: d_{G}^{+}(1) = 1, d_{G}^{−}(1) = 1, d_{G}^{+}(2) = 2, d_{G}^{−}(2) = 0, d_{G}^{+}(3) = 0, d_{G}^{−}(3) = 2. All’endofunzione f : [n] → [n] associamo ora il grafo diretto G_{f} = (V (G_{f}), E(G_{f})) ponendo V (G_{f}) = [n] e mettendo un arco orientato da a verso b se b = f(a), i.e.

E(G_{f}) = {(a, f(a)) : a ∈ [n]}.

Ad esempio per n = 5 ed f descritta da

\begin{matrix}a & 1 & 2 & 3 & 4 & 5 \\ f(a) & 1 & 3 & 4 & 4 & 3 \end{matrix}

si ottiene il grafo diretto seguente:

1  3 4 5 2

Torniamo alla discussione precedente, dove ora, fissata una particolare endofunzione f, abbiamo costruito il grafo diretto G_{f} ad essa associato.

Proposizione 2.7 Il grafo non orientato indotto dal sottoinsieme di vertici V (T_{x}) nel grafo orientato G_{f} è un albero, per ogni x ∈ R_{f}.

Dimostrazione. Con un abuso di notazione, indichiamo con T_{x} il grafo indotto da V (T_{x}) in G_{f}. Verifichiamo prima la connessione di T_{x}. Se un elemento a ∈ [n]\R_{f} ha come punto di contatto x = f^{s}(a), allora questo è il primo ricorrente della sequenza a, f(a), f^{2}(a), …: questo implica che le coppie (a, f(a)), (f(a), f^{2}(a)) e così via sono archi del grafo orientato G_{f}. Inoltre anche gli elementi f^{i}(a), con i < s, hanno x come punto di contatto: pertanto

a, {a, f(a)} , f(a), {f(a), f^{2}(a)} , f^{2}(a), …, {f^{s−1}(a), x} , x

è un cammino in T_{x} tra a ed x. Allora gli elementi che hanno punto di contatto in x, essendo connessi tutti ad x, sono anche connessi tra di loro. Per ogni a ∈ V (T_{x}) con a diverso da x, esiste un solo arco uscente (a, f(a)), poiché f(a) è univocamente definito (f è una funzione). Allora |E(T_{x})| = |T_{x} − {x}|, quindi, per il Teorema 1.9, T_{x} è un albero. _{□} Dimostrazione. (Teorema di Joyal) Le Proposizioni 2.5 e 2.7 ci dicono che, fissata un’endofunzione, resta ad essa associata una terna (R_{f}, f|_{R_{f}} , {T_{x}}_{x∈R_{f}}), formata da un sottoinsieme di [n], una biiezione su questo sottoinsieme (è la restrizione di f a questo sottoinsieme) e una famiglia, indicizzata dagli elementi del sottoinsieme, di alberi radicati, a due a due disgiunti, i cui vertici "ricoprono" [n]. Viceversa data una terna (V, g, {T_{y}}_{y∈V}), con V ⊆ [n], g : V → V biiezione di V e una famiglia di alberi radicati con le proprietà suddette, si può costrire un’endofunzione (perché?). Abbiamo visto precedentemente che un vertebrato si scompone in modo del tutto analogo come una terna (C ⊆ [n], <, {T_{x}}_{x∈C}) ma il secondo elemento della terna, piuttosto che essere una biiezione su un sottoinsieme di [n], è un ordinamento lineare. Ricordiamo ora che il numero di ordinamenti lineari di un fissato insieme A è |A|! e che tale è anche il numero di biiezioni di A: si ottiene pertanto una corrispondenza biunivoca tra terne del tipo "sottoinsieme-biiezione-famiglia di alberi" corrispondenti a endofunzioni e terne del tipo "sottoinsieme-ordinamento lineare-famiglia di alberi" corrispondenti a vertebrati, ovvero una corrispondenza biunivoca F_{n} → V_{n}. _{□}

2.4 Coefficienti multinomiali

Richiamiamo la definizione del coefficiente binomiale. Sia n un numero naturale, x e y due indeterminate. Si consideri la potenza n-sima del binomio (x + y):

\begin{aligned}(x + y)^{n} & = & \underbrace{(x + y) ⋯ (x + y)} . \\ & & n volte \end{aligned}

Detta potenza, per la proprietà distributiva del prodotto, si può riscrivere come

(x + y)^{n} = ∑ z_{1}z_{2} … z_{n}  (2.5)

dove la somma si estende alle stringhe distinte di lunghezza n con z_{i} ∈ {x, y}. Se nella stringa z_{1}z_{2} … z_{n} ∈ {x, y}^{n} vi sono h occorrenze della variabile x e quindi n − h occorrenze della variabile y, poiché le variabili commutano, possiamo scrivere z_{1}z_{2} … z_{n} = x^{h}y^{n−h}. Raggruppiamo nella somma (2.5) tutti i monomi del tipo x^{h}y^{n−h} e indichiamo con \binom{n}{h} il coefficiente di detto monomio (da qui il nome di coefficiente binomiale!):

(x + y)^{n} = ∑_{h=0}^{n} \binom{n}{h}x^{h}y^{n−h}.  (2.6)

Osservazione 1. Dalla discussione precedente risulta subito che \binom{n}{h} è il numero di stringhe di lunghezza n su un alfabeto a due simboli con h occorrenze di un simbolo e n − h occorrenze dell’altro simbolo. Questo fornisce una prima interpretazione combinatoria del coefficiente binomiale, dalla quale si deduce ad esempio che

\binom{n}{h} = \binom{n}{n − h}  (2.7)

Infatti data una qualunque stringa \underline{z} = z_{1} … z_{n} con h occorrenze di x si associ la stringa \underline{z}′ ottenuta scambiando le x con le y e viceversa. Questa applicazione è ovviamente biunivoca e le occorrenze di x e y in \underline{z}′ sono rispettivamente n − h ed h. (Un altro modo di dimostrare la (2.7) è osservare che il polinomio (x + y)^{n} è simmetrico nelle variabili x e y.) Osservazione 2. In effetti si potrebbe denotare il coefficiente del monomio di tipo x^{h}y^{n−h} come

\binom{n}{h, n − h} = \binom{n}{h}.

Se 0 ≤ h, k ≤ n sono tali che h + k = n, la relazione (2.7) si traduce in

\binom{n}{h, k} = \binom{n}{k, h}  (2.8)

La (2.6) si può anche scrivere come

(x + y)^{n} = ∑_{{h,k \atop h+k=n}}^{n} \binom{n}{h, k}x^{h}y^{k}.  (2.9)

Osservazione 3. Ad ogni fissata stringa z_{1}z_{2} … z_{n} ∈ {x, y}^{n} possiamo associare un sottoinsieme I ⊆ [n] nel seguente modo: se z_{i} = x allora i ∈ I. In realtà ogni stringa z_{1}z_{2} … z_{n} determina una bipartizione (I, J) di [n], ovvero due sottoinsiemi I, J tali che I ∩ J = ∅ e I ∪ J = [n], dove i ∈ I se z_{i} = x e i ∈ J se z_{i} = y. Inoltre |I| è pari al numero di occorrenze di x in z_{1}z_{2} … z_{n}, mentre |J| = n − |I| è il numero di occorrenze di y in z_{1}z_{2} … z_{n}. Poiché le indeterminate x e y commutano, si ha z_{1}z_{2} … z_{n} = x^{|I|}y^{|J|}. Sostituendo nella (2.5):

(x + y)^{n} = ∑_{I,J bipartizione di [n]} x^{|I|}y^{|J|} = ∑_{h=0}^{n} ∑_{{I⊆[n] \atop |I|=h}} x^{h}y^{n−h}  (2.10)

e dal confronto di (2.6) con (2.10) si deduce che \binom{n}{h} è il numero di sottoinsiemi di cardinalità h in un insieme di cardinalità n e quindi con le notazioni di (1.1):

\binom{n}{h} = |\binom{[n]}{h}| .

Proposizione 2.8 Per n naturale e 0 ≤ h ≤ n si ha

\binom{n}{h} = \frac{n!}{h!(n − h)!}  (2.11)

Dimostrazione. Utilizziamo la precedente interpretazione combinatoria del binomiale, ovvero \binom{n}{h} è pari al numero di sottoinsiemi di cardinalità h in [n]. Per formare un tale insieme A, abbiamo n scelte possibili per il primo elemento a_{1} , n − 1 scelte tra i residui n−1 elementi per il secondo elemento a_{2}, etc. fino all’h-simo elemento a_{h} che può essere scelto arbitrariamente in n−(h−1) modi diversi tra i rimanenti n−(h−1) candidati. Si osservi però che in questo modo si sono costruite "liste" (a_{1}, …, a_{h}) di elementi di [n] lunghe h piuttosto che sottoinsiemi, per un totale di

n(n − 1) ⋯ (n − h + 1) = \frac{n!}{(n − h)!}  (2.12)

liste diverse. Si noti che ogni riordinamento di (a_{1}, …, a_{h}) dà luogo allo stesso sottoinsieme A = {a_{1}, …, a_{h}}; poiché vi sono esattamente h! modi diversi di riordinare la lista data, occorre dividere la quantità in (2.12) per h!, da cui segue la (2.11). _{□}

Proposizione 2.9 I coefficienti binomiali verificano la seguente ricorsione:

\binom{n}{h} = \binom{n − 1}{h} + \binom{n − 1}{h − 1}.  (2.13)

Dimostrazione. Si può dimostrare questa identità in modo combinatorio. Suddividiamo tutti i sottoinsiemi di [n] di cardinalità h nelle seguenti due famiglie:

S_{1} = \{A ∈ \binom{[n]}{h} : n ∈ A\}

S_{2} = \{A ∈ \binom{[n]}{h} : n ∉ A\}

Naturalmente vale

S_{1} ∪ S_{2} = \binom{[n]}{h}, S_{1} ∩ S_{2} = ∅  (2.14)

Inoltre le applicazioni

S_{1} → \binom{[n − 1]}{h − 1}
A ↦ A \ {n}

e

S_{2} → \binom{[n − 1]}{h}
A ↦ A

sono biiezioni, da cui

|S_{1}| = \binom{n − 1}{h − 1} e |S_{2}| = \binom{n − 1}{h};  (2.15)

da (2.14) e (2.15) segue (2.13). _{□}

Utilizziamo la formula ricorsiva precedente per calcolare i primi valori del coefficiente binomiale.

n
0  1
1  1  1
2  1  2  1
3  1  3  3  1
4  1  4  6  4  1
5 1  5  10  10  5  1

Vediamo un’altra identità soddisfatta dai coefficienti binomiali.

Proposizione 2.10

(n − h)\binom{n}{h} = \binom{n}{h + 1}(h + 1)  (2.16)

Dimostrazione. Utilizziamo ancora una volta la tecnica del doppio conteggio. Sia

B = \{(a, A) : a ∈ A, A ∈ \binom{[n]}{h + 1}\}

la famiglia di tutte le coppie “capo tribù - tribù”, dove le possibili tribù hanno popolazione h + 1 e sono state formate scegliendone gli appartenenti da un insieme fissato di n individui. Calcoliamo la cardinalità di B in due modi diversi: un primo modo è quello di scegliere prima la popolazione della tribù su cui il capo “regnerà”: vi sono \binom{n}{h} modi diversi di farlo; poi si sceglie all’esterno il capo della tribù fra i rimanenti n − h individui, per un totale di

|B| = (n − h)\binom{n}{h}.

Un secondo modo è di stabilire prima qual è complessivamente la tribù: ci sono \binom{n}{h+1} scelte distinte. A questo punto dobbiamo scegliere all’interno della tribù un suo capo: possiamo scegliere arbitrariamente tra gli h + 1 appartenenti per un totale di

|B| = (h + 1)\binom{n}{h + 1}.

Confrontando le due uguglianze di ottiene la (2.16). _{□} Proposizione 2.11 Per ogni fissato naturale n la successione

\binom{n}{0}, \binom{n}{1}, …, \binom{n}{h}, …, \binom{n}{n − 1}, \binom{n}{n}  (2.17)

è crescente per h = 0, 1, …, ⌊\frac{n}{2}⌋ − 1, decrescente per h = ⌊\frac{n}{2}⌋, …, n − 1, n (ovvero è unimodale).

Dimostrazione. Essendo tale successione simmetrica per (2.7), è sufficiente dimostrare che

\binom{n}{h} < \binom{n}{h + 1}, h = 0, …, ⌊\frac{n}{2}⌋ − 1.  (2.18)

Ma per la (2.16) si ha

\begin{matrix}( & {n \atop h} & ) \\ ( & {n \atop h+1} & ) \end{matrix} = \frac{h + 1}{n − h}.

Ora

\frac{h + 1}{n − h} < 1 ⇔ h + 1 < n − h ⇔ 2h < n − 1 :

analizzando distintamente i casi in cui n è pari oppure dispari si arriva comunque alla conclusione che h < ⌊\frac{n}{2}⌋. _{□}

Corollario 2.12

\binom{n}{⌊\frac{n}{2}⌋} = max \{\binom{n}{h} : h = 0, …, n\}  (2.19)

Osservazione. Se n è dispari allora ⌊\frac{n}{2}⌋ ≠ ⌈\frac{n}{2}⌉ = ⌊\frac{n}{2}⌋ + 1 ma \binom{n}{⌊ \frac{n}{2} ⌋} = \binom{n}{⌈ \frac{n}{2} ⌉}.

A questo punto introduciamo la definizione di coefficiente multinomiale, che generalizza quella di coefficiente binomiale. Si consideri la potenza n-sima del polinomio x_{1} + x_{2} + ⋯ + x_{k}, ove x_{i} sono indeterminate:

\begin{aligned}(x_{1} + x_{2} + ⋯ + x_{k})^{n} & = & \underbrace{(x_{1} + x_{2} + ⋯ + x_{k}) … (x_{1} + x_{2} + ⋯ + x_{k})} . \\ & & n volte \end{aligned}

Espandendo il prodotto degli n fattori, si ha:

(x_{1} + x_{2} … + x_{k})^{n} = ∑ z_{1} ⋯ z_{n}  (2.20)

dove la somma si estende alle stringhe distinte z_{1} … z_{n} di lunghezza n sull’alfabeto {x_{1}, …, x_{k}}. Se nella stringa z_{1}z_{2} … z_{n} ∈ {x_{1}, …, x_{k}}^{n} vi sono r_{1} occorrenze della variabile x_{1}, r_{2} occorrenze della variabile x_{2}, r_{k} occorrenze della variabile x_{k} (e quindi r_{1} + r_{2} + … + r_{k} = n), dato che le variabili commutano possiamo scrivere

z_{1}z_{2} … z_{n} = x_{1}^{r_{1}}x_{2}^{r_{2}} … x_{k}^{r_{k}}.

Raggruppiamo nella somma (2.20) tutti i monomi del tipo x_{1}^{r_{1}}x_{2}^{r_{2}} ⋯ x_{k}^{r_{k}}: il coefficiente di detto monomio nell’espansione della potenza n-sima del polinomio x_{1} + ⋯ + x_{k} si chiama coefficiente multinomiale e viene indicato con

\binom{n}{r_{1}, r_{2}, …, r_{k}}.

Si ha:

(x_{1} + x_{2} ⋯ + x_{k})^{n} = ∑_{{(r_{1},r_{2},... ,r_{k}):r_{i}≥0 \atop r_{1}+r_{2}+...+r_{k}=n}} \binom{n}{r_{1}, r_{2}, …, r_{k}}x_{1}^{r_{1}}x_{2}^{r_{2}} ⋯ x_{k}^{r_{k}}.  (2.21)

Analogamente al coefficiente binomiale, si ha quindi che il numero naturale \binom{n}{r_{1},r_{2},... ,r_{k}} conta il numero di stringhe k-arie di lunghezza n (in questo caso, gli elementi di {x_{1}, …, x_{k}}^{n}) che hanno r_{i} occorrenza del simbolo x_{i}, i = 1, …, k. Osservazione 4. Una k-partizione ordinata di [n] è una successione (A_{1}, A_{2}, … A_{k}) di sottoinsiemi A_{i} ⊆ [n] tali che

A_{i} ∩ A_{j} = ∅, i ≠ j,
A_{1} ∪ A_{2} ∪ … ∪ A_{k} = [n].

Diremo che una k-partizione di [n] è di tipo (r_{1}, r_{2}, …, r_{k}) se |A_{i}| = r_{i} per ogni indice i. Inoltre è facile vedere che c’è una corrispondenza biunivoca tra stringhe

\underline{z} = z_{1}z_{2} … z_{n} ∈ \{x_{1}, …, x_{k}\}^{n}

con r_{i} occorrenze della variabile x_{i} e k-partizioni di [n] di tipo (r_{1}, r_{2}, …, r_{k}). In questa corrispondenza:

\underline{z} = z_{1}z_{2} … z_{n} ↦ (A_{1}, A_{2}, …, A_{k})  (2.22)

dove poniamo

A_{h} = {j : j ∈ [n], z_{j} = x_{h}}.

Illustriamo questa biiezione con un esempio, dove per semplicità si sostituisce l’alfabeto {1, …, k} all’alfabeto {x_{1}, …, x_{k}}. Sia n = 10, k = 4,

\underline{z} = 2241241114.

Con le notazioni precedenti si ha (r_{1}, r_{2}, r_{3}, r_{4}) = (4, 3, 0, 3). La partizione di {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} in quattro sottoinsiemi è (A_{1}, A_{2}, A_{3}, A_{4}) con

A_{1} = {4, 7, 8, 9}; A_{2} = {1, 2, 5}; A_{3} = ∅; A_{4} = {3, 6, 10}.

Si può pertanto dare una seconda interpretazione combinatoria del coefficiente multinomiale: \binom{n}{r_{1},r_{2},... ,r_{k}} conta il numero di partizioni di [n] in k sottoinsiemi (ordinati) di cardinalità rispettiva r_{i}.

Inoltre, fissata una funzione f : [n] → [k], le k controimmagini

f^{−1}(1), f^{−1}(2), …, f^{−1}(k)

formano una partizione dell’insieme [n]. Viceversa, ogni k-partizione ordinata di [n]

(A_{1}, A_{2}, …, A_{k})

induce una funzione g : [n] → [k] definita da g(h) = i se e solo se h ∈ A_{i}. Ne segue che il coefficiente multinomiale \binom{n}{r_{1},r_{2},... ,r_{k}} è il numero di funzioni da un insieme a n elementi in un insieme a k elementi le cui fibre f^{−1}(j) abbiano cardinalità r_{j}, per j = 1, …, k. Osservazione 5. Poiché il ruolo delle variabili nel polinomio (2.20) è simmetrico, si ha:

\binom{n}{r_{1}, r_{2}, …, r_{k}} = \binom{n}{r_{i_{1}}, r_{i_{2}}, …, r_{i_{k}}}  (2.23)

dove i_{1}, i_{2}, …, i_{k} è una qualunque permutazione degli indici degli indici {1, …, k}.

Vediamo ora che anche i coefficienti multinomiali soddisfano una relazione di ricorrenza.

(x_{1} + x_{2} + ⋯ + x_{k})^{n}
= (x_{1} + x_{2} + ⋯ + x_{k})^{n−1}(x_{1} + x_{2} + ⋯ + x_{k})
= (  ∑_{{(s_{1},s_{2},... ,s_{k}) \atop s_{1}+s_{2}+...+s_{k}=n−1}} \binom{n − 1}{s_{1}, s_{2}, …, s_{k}}x_{1}^{s_{1}}x_{2}^{s_{2}} … x_{k}^{s_{k}} ) (x_{1} + x_{2} + ⋯ + x_{k})

= ∑_{j=1}^{k} (  ∑_{{(s_{1},s_{2},... ,s_{k}) \atop s_{1}+s_{2}+...+s_{k}=n−1}} \binom{n − 1}{s_{1}, s_{2}, …, s_{k}}x_{1}^{s_{1}} … x_{j}^{s_{j}+1} … x_{k}^{s_{k}} )

= ∑_{{(s_{1},s_{2},... ,s_{k}) \atop s_{1}+s_{2}+...+s_{k}=n−1}} ∑_{j=1}^{k} \binom{n − 1}{s_{1}, …, s_{j}, …, s_{k}}x_{1}^{s_{1}} … x_{j}^{s_{j}+1} … x_{k}^{s_{k}}

= ∑_{{(r_{1},r_{2},... ,r_{k}) \atop r_{1}+r_{2}+...+r_{k}=n}} ∑_{j=1}^{k} \binom{n − 1}{r_{1}, …, r_{j} − 1, …, r_{k}}x_{1}^{r_{1}} … x_{j}^{r_{j}} … x_{k}^{r_{k}},  (2.24)

dove per comodità sono stati cambiati gli indici di sommatoria ponendo r_{i} = s_{i} se i ≠ j ed r_{j} = s_{j} + 1. Confrontando nella (2.21) e nella (2.24) il coefficiente del monomio x_{1}^{r_{1}} … x_{j}^{r_{j}} … x_{k}^{r_{k}} si ottiene la ricorrenza:

\binom{n}{r_{1}, r_{2}, …, r_{k}} = ∑_{j=1}^{k} \binom{n − 1}{r_{1}, …, r_{j} − 1, …, r_{k}}.  (2.25)

Con molto meno "sudore" algebrico, il lettore può divertirsi a dimostrare la precedente ricorrenza utilizzando una delle interpretazioni combinatorie del multinomiale.

Proposizione 2.13 Dato un naturale n e k interi r_{i} ≥ 0 tali che r_{1} + … + r_{k} = n si ha:

\binom{n}{r_{1}, …, r_{k}} = \frac{n!}{r_{1}! … r_{k}!} .  (2.26)

Dimostrazione. Vogliamo contare quante sono le funzioni di [n] in [k] tali che |f^{−1}(j)| = r_{j}, per j = 1, …, k. Possiamo scegliere la controimmagine f^{−1}(1) in \binom{n}{r_{1}} modi diversi. Restano n − r_{1} elementi, da cui estrarre arbitrariamente un sottoinsieme di cardinalità r_{2} per formare f^{−1}(2), cosa ciò che possiamo fare in \binom{n−r_{1}}{r_{2}} modi diversi etc. In totale il numero di possibilità è:

\binom{n}{r_{1}, …, r_{k}} = \binom{n}{r_{1}}\binom{n − r_{1}}{r_{2}} ⋯ \binom{n − (r_{1} + ⋯ + r_{k−1})}{r_{k}}
= \frac{n!}{r_{1}!(n − r_{1})!} · \frac{(n − r_{1})!}{r_{2}![n − (r_{1} + r_{2})]!} ⋯ \frac{[n − (r_{1} + ⋯ + r_{k−1})]!}{r_{k}![n − (r_{1} + r_{2} + ⋯ + r_{k})]!}

e cancellando i fattori ripetuti a numeratore e denominatore si arriva alla (2.26). _{□}

2.5 Dimostrazione ricorsiva della formula di Cayley

Ci prefiggiamo di calcolare (ancora una volta...!) il numero T (n) degli alberi di copertura di K_{n}. Raffiniamo la nostra ricerca: sia t(n; d_{1}, …, d_{n}) il numero di alberi di copertura di K_{n} i cui vertici, enumerati come {v_{1}, v_{2}, …, v_{n}}, hanno gradi rispettivamente d_{1}, … d_{n}. Dato che un albero è connesso, deve essere

d_{i} ≥ 1, i = 1, …, n.

Si ha perciò che t(n; d_{1}, …, d_{n}) = 0 se almeno uno dei parametri d_{i} è nullo. Osserviamo anche che, per n ≥ 3, tutti i vertici di grado 1 sono adiacenti a vertici di grado almeno 2, altrimenti il grafo non sarebbe connesso. Inoltre per il Teorema 1.9 e per la relazione (1.2) tra gradi e numero di archi in un grafo si ha

d_{1} + d_{2} + … + d_{n} = 2(n − 1) = 2n − 2.  (2.27)

Vale quindi

T (n) = ∑_{(d_{1},...dn):d_{i}≥1 ; ∑_{i} d_{i}=2n−2} t(n; d_{1}, …, d_{n}).  (2.28)

Si deve notare che la successione dei gradi in un albero etichettato (in generale, in un grafo qualunque), non determina il grafo stesso. Si confrontino ad esempio i due alberi su 9 vertici nella figura seguente, che hanno la stessa successione di gradi (1, 1, 1, 3, 3, 3, 1, 2, 1).

7  8  9 4  5  6 1  2  3  7  8  9 4  5  6 1  2  3

Calcoliamo ora i primi valori dei coefficienti t(n; d_{1}, …, d_{n}). Se n = 2, l’unica possibilità per la successione dei gradi è (1, 1), e t(2; 1, 1) = 1. Si ha

v_{1}  v_{2}

Per n = 3, una possibile successione di gradi è (2, 1, 1). In questo caso, se 2 è il grado del vertice v_{1} in un albero T, necessariamente la famiglia

{{v_{1}, v_{2}}, {v_{1}, v_{3}}}

esaurisce gli archi di T, quindi

t(3; 2, 1, 1) = 1 :

v_{2}  v_{1}  v_{3}

Senza perdita di generalità possiamo assumere in quanto segue che d_{i} ≥ d_{i+1}. In tal modo sarà d_{n} = 1, perché un albero ha almeno un vertice di grado 1 (in realtà, ne ha almeno 2, ma qui non serve saperlo!). In effetti, a meno di fare una nuova etichettatura dei vertici, è evidente che:

Proposizione 2.14 Per ogni riordinamento i_{1}, i_{2}, …, i_{n} degli indici si ha:

t(n; d_{1}, …, d_{n}) = t(n; d_{i_{1}}, …, d_{i_{n}}).

Vogliamo dimostrare una relazione di ricorrenza per i numeri in questione.

Proposizione 2.15 Siano n, d_{1}, …, d_{n} interi tali che d_{i} ≥ 1, d_{i} ≥ d_{i+1} e

∑_{i} d_{i} = 2n − 2.

Allora

t(n; d_{1}, …, d_{n}) = ∑_{i=1}^{n−1} t(n − 1; d_{1}, …, d_{i} − 1, …, d_{n−1}).  (2.29)

Dimostrazione. Sia T (n; d_{1}, …, d_{n}) la famiglia degli alberi etichettati sui vertici {v_{1}, …, v_{n}} con successione di gradi (d_{1}, …, d_{n}), quindi

t(n; d_{1}, …, d_{n}) = |T (n; d_{1}, …, d_{n})|;

sia T un suo elemento. Il vertice v_{n} ha grado d_{n} = 1, come osservato precedentemente. Consideriamo l’albero T′ che si ottiene da T cancellando il vertice v_{n} e l’arco (unico!) ad esso adiacente, sia esso {v_{n}, v_{i}} (per quanto osservato all’inizio del paragrafo, sarà d_{i} ≥ 2): T′ è un albero etichettato sugli n − 1 vertici {v_{1}, …, v_{n−1}} con successione di gradi (d_{1}, …, d_{i} − 1, …, d_{n−1}). Viceversa, ogni albero T ∈ T (n; d_{1}, …, d_{n}) si può ottenere a partire da un albero T′ sui vertici {v_{1}, …, v_{n−1}}, aggiungendo il nuovo vertice v_{n}, fissando arbitrariamente un qualunque vertice v_{i} ∈ {v_{1}, …, v_{n−1}} con d_{T′}(v_{i}) = d_{i} − 1 e aggiungendo l’arco {v_{n}, v_{i}}. _{□}

T  v_{n}  T′  v_{i}

Osservazione. Per la Proposizione 2.14, la ricorsione (2.29) vale anche se d_{i} ≱ d_{i+1}.

Mettiamo ora insieme i vari pezzi del puzzle per capire il quadro finale. Dimostrazione. (Teorema di Cayley) Affermiamo che

t(n; d_{1}, …, d_{n}) = \binom{n − 2}{d_{1} − 1, …, d_{n} − 1}.  (2.30)

Anzitutto, se d_{i} ≥ 1 per ogni i = 1, …, n e se vale

∑_{i} d_{i} = 2n − 2

allora d_{i} − 1 ≥ 0 per ogni i = 1, …, n e si ha

∑_{i}(d_{i} − 1) = ∑_{i} d_{i} − ∑_{i} 1 = 2n − 2 − n = n − 2,

quindi il multinomiale al membro destro è ben definito. Ora le due sequenze di numeri in (2.30) coincidono nei termini iniziali: infatti abbiamo già calcolato in (2.5) che per n = 3 vale t(3; 2, 1, 1) = 1. Inoltre, usando la formula (2.26) si ha che

\binom{3 − 2}{2 − 1, 1 − 1, 1 − 1} = \binom{1}{1, 0, 0} = \frac{1!}{1! · 0! · 0!} = 1.

D’altro canto le due sequenze soddisfano la stessa relazione ricorsiva, come si vede confrontando la (2.29) e la (2.25). Per induzione quindi segue la (2.30).

Infine, la (2.21) è un’equazione polinomiale, vera per ogni valore delle indeterminate e per ogni valore naturale di n e k. In particolare, sostituendovi n − 2 al posto di n, n al posto di k e ponendo x_{i} = 1 per ogni i si può scrivere:

n^{n−2} = ∑_{(r_{1},... ,rn) ; ∑_{i} r_{i}=n−2} \binom{n − 2}{r_{1}, …, r_{n}}

per (2.30) = ∑_{(r_{1},... ,rn) ; ∑_{i} r_{i}=n−2} t(n; r_{1} + 1, …, r_{n} + 1)

per (2.28) = T (n).
□

Osservazione. Riprendiamo per un momento il codice di Prüfer: se analizziamo la carriera di un vertice qualsiasi nella sequenza a_{1}, …, a_{n−2} di codifica di un albero T di vertici [n] e gradi (d_{1}, …, d_{n}) ci accorgiamo che, ogni volta che il vertice x ∈ V (T) con d_{T} (x) ≥ 2 perde un arco nella potatura, esso appare nella sequenza, finché non diventa di grado 1: in totale quindi esso appare d_{T} (x) − 1 volte. Con questo ragionamento dovrebbe essere chiaro che t(n, d_{1}, … d_{n}) è pari al numero delle stringhe in [n]^{n−2} in cui la lettera i compare d_{i} − 1 volte: ora sappiamo che questo numero è il coefficiente multinomiale

\binom{n − 2}{d_{1} − 1, d_{2} − 1, …, d_{n} − 1}.

2.6 Ordinamenti e permutazioni

Chiamiamo permutazione dell’insieme [n] ogni biiezione f : [n] → [n]. Ricordiamo che vi sono n! biiezioni di [n] in sé. Spesso è comodo indicare la biiezione tramite una matrice bidimensionale, sulla cui seconda riga si leggono le immagini dei corrispondenti elementi della prima riga. Esempio 1. Sia

f = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 7 & 5 & 3 & 6 & 2 & 4 & 1 \end{matrix} ) ,

ovvero f(1) = 7, f(2) = 5 etc. Il corrispondente grafo diretto G_{f} è

1  7  2  5  3  4  6

Esempio 2. Sia

f = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 4 & 5 & 7 & 6 & 3 & 1 \end{matrix} ) .

Il corrispondente grafo diretto G_{f} è

2  4  7 1  5  6 3

Nei grafi diretti un ciclo diretto è un sottografo connesso in cui ogni vertice ha grado uscente e grado entrante pari ad 1. Si nota dagli esempi che il grafo diretto corrispondente alle due permutazioni è unione disgiunta di cicli diretti. Questa non è una coincidenza, come vedremo infatti nella seguente:

Proposizione 2.16 Il grafo diretto G_{f} corrispondente a una permutazione ha la proprietà che ogni vertice del grafo appartiene ad un unico ciclo di G_{f}.

Dimostrazione. Ricordiamo le definizioni (2.3) e (2.4). In questo caso, dato che f è biiettiva, si deve avere d_{G}^{+}(x) = d_{G}^{−}(x) = 1: se esistesse un vertice x appartenente a più cicli, si avrebbe d_{G}^{+}(x) ≥ 2 oppure d_{G}^{−}(x) ≥ 2. _{□}

I punti fissi di una permutazione sono gli elementi a ∈ [n] tali che f(a) = a. Nel grafo della permutazione, l’arco (a, a) corrispondente ad un punto fisso a è un cappio sul vertice a. La permutazione identica su n elementi, denotata qui da id_{n}, ha solo punti fissi,

id_{n} = ( \begin{matrix}1 & 2 & … & i & … & n \\ 1 & 2 & … & i & … & n \end{matrix} ) ,

e il suo grafo G_{id_{n}} ha solo cappi:

1  2  …  i  …  n

Date due permutazioni su n elementi f e g si può definire il loro prodotto funzionale, la composizione f ⋆ g : [n] → [n] delle due permutazioni, come:

(f ⋆ g)(i) = g(f(i)).

Si noti l’ordine con cui componiamo le permutazioni: si applica prima la funzione f, poi la funzione g all’immagine secondo f. Ad esempio per

f = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 7 & 5 & 3 & 6 & 2 & 4 & 1 \end{matrix} ) ,

g = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 4 & 5 & 7 & 6 & 3 & 1 \end{matrix} ) ,

si ottiene (f ⋆ g)(1) = g(f(1)) = g(7) = 1, (f ⋆ g)(2) = g(f(2)) = g(5) = 6 etc. quindi

f ⋆ g = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 6 & 5 & 3 & 4 & 7 & 2 \end{matrix} ) .

Attenzione! Il prodotto di composizione di permutazioni non è commutativo. Se f e g sono come sopra, si ha

g ⋆ f = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 5 & 6 & 2 & 1 & 4 & 3 & 7 \end{matrix} ) .

Denotiamo anche, come di consueto, f^{k} := f ⋆ f ⋆ … ⋆ f, k volte.

Uno scambio (o trasposizione) su V è una permutazione f per cui esistono due elementi distinti a, b ∈ [n] con f(a) = b, f(b) = a e f(x) = x se x ∉ {a, b}. Il grafo corrispondente si compone di un solo ciclo su due elementi e di cappi sugli altri vertici. Ad esempio, per

f = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 5 & 3 & 4 & 2 & 6 & 7 \end{matrix} ) ,

si ha

2  ^{5}  _{1}  _{3}  _{4}  _{6}  _{7}  G_{f}

Sia C(f) l’insieme dei cicli di lunghezza almeno 2 del grafo G_{f} di una fissata permutazione f (si escludono quindi i cappi). Per ogni C ∈ C(f) denotiamo con f_{C} la biiezione di [n] indotta dal ciclo C, ovvero

f_{C}(a) = \{ \begin{matrix}f(a) & se a ∈ C, \\ a & altrimenti. \end{matrix}

Poiché abbiamo escluso i cappi, se a è un vertice del ciclo C allora f(a) ≠ a. La permutazione f_{C} è la restrizione di f al sottoinsieme dei vertici del ciclo. Se per una permutazione f l’insieme C(f) consiste di un solo ciclo C, allora f coincide con f_{C}. In particolare f può essere descritta dalla sequenza delle immagini successive di un fissato vertice a del ciclo C: (a, f_{C}(a), f_{C}^{2}(a) …, f_{C}^{t}(a)), ove t è il minimo intero positivo tale che f_{C}^{t+1}(a) = a. Questo tipo di permutazioni è chiamato permutazione ciclica. Viceversa, fissata una lista (a_{1}, a_{2}, …, a_{t}) di interi positivi distinti, si può definire per ogni n ≥ max{a_{i} : 1 ≤ i ≤ t} una permutazione f : [n] → [n] tramite:

\begin{aligned}f(j) & := & j se j ∈ [n] \ \{a_{1}, …, a_{t}\} \\ f(a_{i}) & := & a_{i+1}, i = 1, …, t − 1 \\ f(a_{t}) & := & a_{1}. \end{aligned}

Tale permutazione è ciclica. Uno scambio è dunque una permutazione ciclica che muove due elementi. Si noti che il prodotto di permutazioni cicliche (a_{1}, …, a_{s}) e (b_{1}, …, b_{t}) è commutativo se {a_{1}, …, a_{s}} ∩ {b_{1}, …, b_{t}} = ∅. Ad esempio:

(f_{(1,2,3)} ⋆ f_{(1,2)})(1) = f_{(1,2)}(f_{(1,2,3)}(1)) = f_{(1,2)}(2) = 1

mentre

(f_{(1,2)} ⋆ f_{(1,2,3)})(1) = f_{(1,2,3)}(f_{(1,2)}(1)) = f_{(1,2,3)}(2) = 3.

Si ha

(1, 2, 3) ⋆ (1, 2) = (2, 3) ≠ (1, 3) = (1, 2) ⋆ (1, 2, 3).

Ancora: se f è la permutazione ciclica (1, 2, 3), allora

(1, 2, 3)^{2} = (1, 3, 2),
(1, 2, 3)^{3} = id,
(1, 2, 3, 4)^{2} = (1, 3) ⋆ (2, 4).

Per comodità indicheremo il prodotto di due (o più) permutazioni cicliche come (a_{1}, …, a_{s})(b_{1}, …, b_{t}) piuttosto che (a_{1}, …, a_{s}) ⋆ (b_{1}, …, b_{t}).

Proposizione 2.17 Ogni permutazione è il prodotto di scambi.

Dimostrazione. Ogni permutazione è rappresentabile come prodotto di permutazioni cicliche: basta allora dimostrare che ogni permutazione ciclica è uguale al prodotto di scambi. Ma questo è subito verificato poiché

(a_{1}, a_{2}, …, a_{k}) = (a_{1}, a_{2})(a_{1}, a_{3}) … (a_{1}, a_{k}).

Osservazione. La decomposizione di un ciclo in prodotto di scambi non è unica. Ad esempio, si verifichi che (1, 3, 2, 4) = (1, 3)(1, 2)(1, 4) = (2, 3)(1, 4)(4, 3) = (1, 3)(2, 3)(1, 2)(1, 4)(4, 3).

Un’inversione per una permutazione π : [n] → [n] è una coppia non ordinata {i, j} ⊆ [n] tale che

(i − j)(π(i) − π(j)) < 0.

In modo ovviamente equivalente, ogni coppia ordinata (i, j) con i, j ∈ [n], i < j tale che π(i) > π(j) dà luogo a un’inversione. Chiamiamo parità di una permutazione π : [n] → [n] la parità del numero di inversioni di π, e la denotiamo con par(π), cioè par(π) ∈ {0, 1} e par(π) ≡ |{(i, j) : i < j, π(i) > π(j), 1 ≤ i, j ≤ n}| (mod 2). Diremo quindi che una permutazione π è pari se par(π) ≡ 0 (mod 2), dispari se par(π) ≡ 1 (mod 2). Ad esempio se

π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 5 & 6 & 2 & 7 & 4 & 1 \end{matrix} ) ,

l’insieme delle sue inversioni è

{(1, 4), (1, 7), (2, 4), (2, 6), (2, 7), (3, 4), (3, 6), (3, 7), (4, 7), (5, 6), (5, 7), (6, 7)},

quindi poiché 12 ≡ 0 (mod 2), si ha par(π) = 0 cioè π è pari. Si noti che l’identità

id_{n} = ( \begin{matrix}1 & 2 & … & n − 1 & n \\ 1 & 2 & … & n − 1 & n \end{matrix} )

ha 0 inversioni, quindi è pari. La permutazione col massimo numero di inversioni è

ρ = ( \begin{matrix}1 & 2 & … & n − 1 & n \\ n & n − 1 & … & 2 & 1 \end{matrix} ) :

infatti è chiaro che ogni coppia (i, j) con i < j forma un’inversione: il numero di inversioni di ρ è allora \binom{n}{2}.

In generale calcolare la parità di una permutazione enumerando tutte le inversioni potrebbe essere piuttosto lungo! Vediamo allora come poter calcolare la parità direttamente dalle lunghezze dei cicli che appaiono nella scrittura in cicli della permutazione.

Teorema 2.18 Sia π una permutazione ed a ≠ b: allora la permutazione π ⋆ (a, b) ha parità diversa da quella di π.

Dimostrazione. L’enunciato equivale a dimostrare che la differenza tra il numero di inversioni di π e di π ⋆ (a, b) è dispari. Poiché (a, b) = (b, a), si può sempre supporre che π^{−1}(a) < π^{−1}(b) e quindi si può scrivere la permutazione π come

π = ( \begin{matrix}1 & … & π^{−1}(a) & … & π^{−1}(b) & … & n \\ π(1) & … & a & … & b & … & π(n) \end{matrix} ) .

40 CAPITOLO 2. ALBERI, FORESTE E PERMUTAZIONI

Se moltiplichiamo π per lo scambio (a, b) si ha evidentemente

π̂ := π ⋆ (a, b) = ( \begin{matrix}1 & … & π^{−1}(a) & … & π^{−1}(b) & … & n \\ π(1) & … & b & … & a & … & π(n) \end{matrix} ) .

Può essere comodo pensare a un’inversione di π come a una coppia di colonne

\{\binom{i}{π(i)}, \binom{j}{π(j)}\}

per le quali valga la condizione suddetta

(i − j)(π(i) − π(j)) < 0.

Sia I l’intervallo della matrice 2 × n di π che ha come estremi le colonne

\binom{π^{−1}(a)}{a} e \binom{π^{−1}(b)}{b}.

Se indichiamo con t il numero di inversioni di π in cui non figura nessuna delle colonne al bordo \binom{π^{−1}(a)}{a} oppure \binom{π^{−1}(b)}{b}, allora t è anche il numero di inversioni di π ⋆

(a, b) in cui non figura nessuna delle colonne al bordo \binom{π^{−1}(a)}{b} o \binom{π^{−1}(b)}{a}. Se

\binom{π^{−1}(i)}{i} è una colonna esterna all’intervallo I, essa è in inversione con \binom{π^{−1}(a)}{a}

se e solo se lo è con \binom{π^{−1}(b)}{a} = \binom{π̂^{−1}(a)}{a}, poiché (π^{−1}(i) − π^{−1}(a)) ha lo stesso segno di (π^{−1}(i)−π^{−1}(b)) e quindi (π^{−1}(i)−π^{−1}(a))(i−a) e (π^{−1}(i)−π^{−1}(b))(i−b) hanno lo stesso segno. Lo stesso vale per le inversioni con \binom{π^{−1}(b)}{b}.

Sia s il numero delle inversioni di π che coinvolgono una colonna esterna ad I e una al bordo di I (cioè una delle due \binom{π^{−1}(a)}{a} e \binom{π^{−1}(b)}{b}). Per quanto detto, s è anche il numero delle inversioni di π̂ che coinvolgono una colonna fuori di I, e

\binom{π^{−1}(a)}{a} oppure \binom{π^{−1}(b)}{b}.

Dimostreremo ora che se consideriamo tutte le coppie di colonne interne all’intervallo I e una delle quali sia al bordo di I, tranne la coppia per π

\{\binom{π^{−1}(a)}{a}, \binom{π^{−1}(b)}{b}\} ,

ovvero per π ⋆ (a, b) la coppia

\{\binom{π^{−1}(a)}{b}, \binom{π^{−1}(b)}{a}\} ,

2.6. ORDINAMENTI E PERMUTAZIONI 41 un numero pari di queste cambia situazione nel passaggio da π a π ⋆ (a, b). Classifichiamo a tal fine le colonne interne ad I, relativamente alla permutazione π, tramite i seguenti insiemi:

• R(a): colonne che sono in inversione con \binom{π^{−1}(a)}{a} ma non con \binom{π^{−1}(b)}{b};

• R(b): colonne che sono in inversione con \binom{π^{−1}(b)}{b} ma non con \binom{π^{−1}(a)}{a};

• R(a, b): colonne che sono in inversione sia con \binom{π^{−1}(a)}{a} che con \binom{π^{−1}(b)}{b};

• N(a, b): colonne che non sono in inversione né con \binom{π^{−1}(a)}{a} né con

\binom{π^{−1}(b)}{b}.

Analogamente per la permutazione π̂ indichiamo con R̂(a) l’insieme delle colonne interne ad I che sono in inversione con \binom{π̂^{−1}(a)}{a} ma non con \binom{π̂^{−1}(b)}{b} etc. Sia inoltre

χ(a, b) = \{ \begin{matrix}1 & se \{\binom{π^{−1}(a)}{a}, \binom{π^{−1}(b)}{b}\} è un’inversione per π \\ 0 & altrimenti \end{matrix}

Chiaramente se

\binom{π^{−1}(a)}{a} e \binom{π^{−1}(b)}{b}

sono in inversione per π, allora le colonne

\binom{π^{−1}(a)}{b} e \binom{π^{−1}(b)}{a}

non lo sono per π ⋆ (a, b) e viceversa. Inoltre

\binom{π^{−1}(i)}{i} ∈ R(a) ⇔ \binom{π^{−1}(i)}{i} ∈ R̂(b),  (2.31)
\binom{π^{−1}(i)}{i} ∈ R(b) ⇔ \binom{π^{−1}(i)}{i} ∈ R̂(a),  (2.32)
\binom{π^{−1}(i)}{i} ∈ R(a, b) ⇔ \binom{π^{−1}(i)}{i} ∈ N̂(a, b),
\binom{π^{−1}(i)}{i} ∈ N(a, b) ⇔ \binom{π^{−1}(i)}{i} ∈ R̂(a, b).  (2.33)

Quindi se calcoliamo le inversioni di π e π̂ rispettivamente, si ha:

inv(π) = t + s + |R(a)| + |R(b)| + 2|R(a, b)| + χ(a, b),
inv(π̂) = t + s + |R̂(a)| + |R̂(b)| + 2|R̂(a, b)| + (1 − χ(a, b)),

per cui da (2.31), (2.32) e (2.33) si ottiene:

inv(π̂) = t + s + |R(b)| + |R(a)| + 2|N(a, b)| + (1 − χ(a, b))

da cui, per differenza:

inv(π̂) − inv(π) = 2(|N(a, b)| − |R(a, b)| − χ(a, b)) + 1

ovvero, un numero dispari. _{□}

Corollario 2.19 Se la permutazione π è rappresentata dal prodotto di r scambi π = (a_{1}, b_{1}) … (a_{r}, b_{r}) allora par(π) ≡ r (mod 2).

Dimostrazione. Si applichi l’induzione su r, tenuto conto che l’identità è pari e che π = id(a_{1}, b_{1}) … (a_{r}, b_{r}). _{□}

Proposizione 2.20 Se π = π_{1} · π_{2} allora par(π) ≡ par(π_{1}) + par(π_{2}) (mod 2).

Dimostrazione. Esprimiamo le due permutazioni π_{1} e π_{2} come prodotto di scambi: se π_{1} = (c_{1}, d_{1}) … (c_{t}, d_{t}) e π_{2} = (e_{1}, g_{1}) … (e_{s}, g_{s}) allora

π = (c_{1}, d_{1}) … (c_{t}, d_{t})(e_{1}, g_{1}) … (e_{s}, g_{s})

è una rappresentazione di π come prodotto di t + s scambi; quindi ricordando che la classe di congruenza (modulo un intero) della somma di due numeri è la somma delle classi di congruenza dei due interi, segue

par(π) ≡ t + s ≡ par(π_{1}) + par(π_{2}) (mod 2).
□

Consideriamo adesso una permutazione qualunque π e sia C = ⋃_{i=1}^{t} C_{i} la sua decomposizione ciclica (attenzione! qui si prendono anche i cicli di lunghezza 1): vogliamo esprimere la sua parità in funzione della decomposizione. La parità di un ciclo C_{i} è (|C_{i}| − 1) (mod 2). Da questo e dalla Proposizione 2.20 si deduce che la parità di π è

par(π) ≡ ∑_{i=1}^{t}(|C_{i}| − 1) ≡ (∑_{i=1}^{t} |C_{i}|) − t ≡ (n − t) (mod 2).

Colorazione di grafi

3.1 Alcune definizioni

Una colorazione di un grafo semplice G è una funzione f : V (G) → C dai vertici del grafo in un insieme astratto C, tale che due vertici adiacenti non abbiano mai lo stesso valore: se {a, b} ∈ E(G) allora f(a) ≠ f(b). Si usa chiamare colori gli elementi di f(V (G)).

Il numero cromatico di un grafo G, denotato con χ(G), è la minima cardinalità possibile di un insieme di colori utilizzati in una colorazione:

χ(G) = min{|f(V (G))| : f colorazione di G}.

Proposizione 3.1 Se F ⊆ G è un sottografo di G allora

χ(F) ≤ χ(G).  (3.1)

Dimostrazione. La restrizione ai vertici di F di ogni colorazione di G induce una colorazione di F, ciò che vale in particolare per una colorazione h con χ(G) colori; allora χ(F) ≤ |h(V (F))| ≤ |h(V (G))| = χ(G). _{□}

Diciamo che una clique in un grafo G è un qualunque sottoinsieme K ⊆ V (G) tale che per ogni x, y ∈ K, x ≠ y si ha {x, y} ∈ E(G), ovvero il sottografo G[K] indotto da K in G è completo (cioè E(G) ⊇ \binom{K}{2}). Il numero di clique di un grafo G, denotato qui con ω(G), è la massima cardinalità possibile per una clique di G :

ω(G) = max \{|K| : K ⊆ V (G), \binom{K}{2} ⊆ E(G)\} .

Osservazione. Il numero cromatico del grafo completo su n vertici K_{n} è χ(K_{n}) = n. Da questo e dalla Proposizione 3.1 segue che

ω(G) ≤ χ(G).

Il grafo complementare di un dato grafo G = (V (G), E(G)) è il grafo Ḡ = (V (Ḡ), E(Ḡ)) con V (Ḡ) = V (G) e

E(Ḡ) = \binom{V (G)}{2} \ E(G).

Si noti che gli archi di G e Ḡ forniscono una bipartizione di \binom{V (G)}{2}.

Uno stabile (o coclique) in un grafo G è un sottoinsieme S ⊆ V (G) di vertici tale che per ogni coppia di suoi elementi x ≠ y sia {x, y} ∉ E(G), cioè tale che il sottografo indotto G[S] abbia tutti i suoi vertici isolati. Il concetto di stabile è quindi "duale" a quello di clique: una clique in un grafo G è uno stabile nel grafo complementare \overline{G} e viceversa. Il numero di stabilità di un grafo G, denotato con α(G) è la massima cardinalità possibile per uno stabile di G. Quindi vale:

α(G) = ω(Ḡ).  (3.2)

Sia f : V (G) → C una colorazione. Allora chiaramente il sottoinsieme monocromatico di vertici

f^{−1}(c) = {x ∈ V (G) : f(x) = c}

è uno stabile, per ogni colore c ∈ C. Viceversa, se S ⊆ V (G) è uno stabile di G, S può essere colorato con un unico colore.

3.2 Grafi bipartiti

Un grafo G si dice bipartito se esiste una partizione dei suoi vertici V (G) = V_{1} ∪ V_{2} in due sottoinsiemi disgiunti tale che

{x, y} ∈ E(G) ⇒ x ∈ V_{1}, y ∈ V_{2} oppure x ∈ V_{2}, y ∈ V_{1},

ovvero tra due vertici dello stesso sottoinsieme V_{i} non vi sono archi, per i = 1, 2 (quindi V_{1} e V_{2} sono stabili). Questo concetto si estende in modo naturale a quello di grafo n-partito. Vediamo ora qualche esempio. Un ciclo C su un numero pari di vertici è bipartito: infatti se V (C) = {v_{1}, v_{2}, …, v_{2k}} e

E(C) = {{v_{i}, v_{i+1}} : i = 1, …, 2k − 1} ∪ {v_{2k}, v_{1}}

allora V_{1} = {v_{h} : h è dispari} e V_{2} = {v_{h} : h è pari} danno una bipartizione dei vertici con le proprietà richieste. In figura vediamo un ciclo su 8 vertici in cui i vertici cerchiati sono “bianchi”, gli altri sono “neri”.

C_{8}

Un altro esempio è il grafo bipartito completo su n+m vertici denotato con K_{n,m} dove n, m sono interi positivi: sia V_{1} un qualsiasi insieme con n elementi, V_{2} un insieme disgiunto da V_{1} con m elementi, allora V (K_{n,m}) = V_{1} ∪ V_{2} e

E(K_{n.m}) = {{v_{1}, v_{2}} : v_{1} ∈ V_{1}, v_{2} ∈ V_{2}} .

K_{4,3}

Osservazione. Abbiamo visto che se f è una colorazione di un grafo G allora le controimmagini dei colori definiscono una partizione di V (G) in stabili. Quindi possiamo dire che G è bipartito se e solo se χ(G) ≤ 2.

Un ultimo esempio. Chiamiamo ipercubo di dimensione n il grafo H_{n} i cui vertici sono i sottoinsiemi di un insieme ad n elementi, i.e. V (H_{n}) = 2^{[n]} e due sottoinsiemi sono adiacenti se differiscono per un elemento:

{A, B} ∈ E(H_{n}) ⇔ A ⊆ B e |B \ A| = 1 oppure B ⊆ A e |A \ B| = 1.

Può essere comodo identificare, come già visto, i sottoinsiemi di [n] con le stringhe binarie di lunghezza n dei rispettivi vettori caratteristici (è questione di “gusti”!). Così

V (H_{n}) = {0, 1}^{n},

E(H_{n}) = \{\{\underline{x}, \underline{y}\} : \underline{x}, \underline{y} ∈ \{0, 1\}^{n}, ∑_{i=1}^{n} |x_{i} − y_{i}| = 1\} .

H_{1} 0  1  H_{2} 00  10 01  11  H_{3} 000  100 010  110 001  101 011  111

Proposizione 3.2

χ(H_{n}) = 2.  (3.3)

Dimostrazione. Consideriamo la seguente partizione di V (H_{n}):

P = \{\underline{x} ∈ V (H_{n}) : ∑_{i=1}^{n} x_{i} ≡ 0 (mod 2)\} ,

D = \{\underline{x} ∈ V (H_{n}) : ∑_{i=1}^{n} x_{i} ≡ 1 (mod 2)\} ,

nelle stringhe con un numero pari o con un numero dispari di bit uguali ad 1. Per come è definito l’insieme degli archi, è immediato verificare che P e D sono due stabili di H_{n}, perciò χ(H_{n}) = 2. _{□}

Vediamo ora la seguente caratterizzazione di un grafo bipartito.

Proposizione 3.3 Per un grafo connesso G = (V (G), E(G)) le seguenti affermazioni sono equivalenti:

1. G è bipartito;

2. G non contiene cicli di lunghezza dispari:

Dimostrazione. (1. ⇒ 2.) Sia C = (V (C), E(C)) con V (C) = {v_{1}, v_{2}, …, v_{2k+1}} e

E(C) = {{v_{i}, v_{i+1}} : i = 1, …, 2k} ∪ {v_{2k+1}, v_{1}}

un ciclo di lunghezza dispari di G. Supponiamo che v_{1} ∈ V_{1}: allora necessariamente si deve avere v_{j} ∈ V_{1} se j è dispari mentre v_{j} ∈ V_{2} se j è pari: dunque l’arco {v_{2k+1}, v_{1}} avrebbe entrambi gli estremi in V_{1}, assurdo. Dimostrazione. ( 2. ⇒ 1.) Sia T un albero di copertura di G e fissiamo un qualunque vertice v_{0} ∈ V (G); si definisca

V_{1} = {x ∈ V : d_{T} (x, v_{0}) ≡ 1 (mod 2)}

l’insieme dei vertici a distanza dispari (in T) da v_{0},

V_{2} = {x ∈ V : d_{T} (x, v_{0}) ≡ 0 (mod 2)}

l’insieme dei vertici a distanza pari da v_{0}. Sia f : V (G) → {0, 1} tale che f(x) = 1 se x ∈ V_{1}, f(x) = 0 se x ∈ V_{2}. Tale f è una colorazione propria di T; vediamo inoltre che f è una colorazione anche rispetto a G: se E(T) = E(G), non c’è nulla da dimostrare, altrimenti sia e = {x, y} ∈ E(G) \ E(T). Supponiamo per assurdo che entrambi i vertici abbiano lo stesso colore i = 0: allora il cammino c in T da v_{0} a x e il cammino c′ in T da y a v_{0} sono entrambi entrambi di lunghezza pari, e l’arco e chiuderebbe un ciclo di G di lunghezza dispari (analogamente, se i = 1). _{□}

3.3 Numero cromatico, numero di stabilità, grado

Vediamo che relazione esiste tra numero cromatico e numero di stabilità.

Proposizione 3.4 |V (G)| ≤ χ(G) · α(G)

Dimostrazione. Consideriamo una colorazione minimale f : V (G) → C, cioè tale che |C| = χ(G). In particolare, f è suriettiva. Per comodità possiamo identificare C con l’insieme {1, 2, …, χ(G)}. Raggruppiamo i vertici per colore:

V (G) = ⋃_{i=1}^{χ(G)} f^{−1}(i).

Avendo già osservato che ogni sottoinsieme monocromatico di colori è uno stabile e poiché |S| ≤ α(G) per ogni stabile S di G, si ha:

|V (G)| = ∑_{i=1}^{χ(G)} |f^{−1}(i)| ≤ ∑_{i=1}^{χ(G)} α(G) = χ(G) · α(G)._{□}

Proposizione 3.5 Siano V_{1}, V_{2} una partizione dei vertici V (G) di G. Indichiamo con G_{i} il sottografo indotto in G da V_{i}, per i = 1, 2. Allora

χ(G) ≤ χ(G_{1}) + χ(G_{2}).  (3.4)

Dimostrazione. Siano f_{1} : V_{1} → C_{1} e f_{2} : V_{2} → C_{2} due colorazioni ottimali, cioè |C_{i}| = χ(G_{i}), i = 1, 2, e tali che C_{1} ∩ C_{2} = ∅. Allora la funzione

f : V (G) → C_{1} ∪ C_{2}

definita da f(v) = f_{i}(v) se v ∈ V_{i} per i = 1, 2 è una colorazione di G poiché qualora {v_{1}, v_{2}} ∈ E(G) con v_{i} ∈ V_{i}, abbiamo f(v_{1}) = f_{1}(v_{1}), f_{2}(v_{2}) = f(v_{2}) e quindi f(v_{1}) ≠ f(v_{2}) da cui: χ(G) ≤ |f(V (G))| = |C_{1}| + |C_{2}| = χ(G_{1}) + χ(G_{2}). _{□}

Vediamo ora una prima limitazione per il numero cromatico di un grafo tramite il suo grado. Dato un qualunque sottoinsieme S di vertici di G, con un abuso di linguaggio, indicheremo di seguito con G \ S il sottografo indotto da V (G) \ S in G, ovvero G[V (G) \ S]. Vale il seguente:

Lemma 3.6 Se S è uno stabile massimale di G allora

d(G \ S) < d(G).

Dimostrazione. Se S è massimale, allora per ogni x ∉ S esiste y ∈ S tale che {x, y} ∈ E(G).

S G \ S y  x  G

Ma allora d_{G\S}(x) < d_{G}(x) per ogni x (vedi figura). _{□}

Proposizione 3.7

χ(G) ≤ d(G) + 1.  (3.5)

Dimostrazione. L’idea è di costruire una colorazione "miope" del grafo, colorando prima uno stabile massimale, e colorando ricorsivamente ciò che resta. La dimostrazione procede quindi per induzione sul grado del grafo. Se d(G) = 0, allora G è totalmente sconnesso, e un colore è sufficiente per colorarlo, quindi χ(G) = 1 = d(G) + 1. Supponiamo ora che d(G) > 0. Sia S_{1} uno stabile massimale in G. Allora per il Lemma 3.6 si ha d(G \ S_{1}) < d(G), o equivalentemente d(G \ S_{1}) + 1 ≤ d(G). Si può applicare adesso l’induzione al grafo G \ S_{1}, e ricordando la Proposizione 3.5 si ha

χ(G) ≤ χ(S_{1}) + χ(G \ S_{1})
(S_{1} è uno stabile) = 1 + χ(G \ S_{1})
(induzione su G \ S_{1}, di grado più basso) ≤ 1 + d(G \ S_{1}) + 1 ≤ d(G) + 1.
□

Abbiamo detto che ω(G) ≤ χ(G), e con la limitazione precedente si può dire che

ω(G) ≤ χ(G) ≤ d(G) + 1.

Bruce Reed in [12] congettura che

χ(G) ≤ ⌈\frac{ω(G) + d(G) + 1}{2}⌉ .

Citiamo infine due esempi in cui vale l’uguaglianza nella relazione (3.5). Il primo è il grafo completo, per il quale abbiamo già visto che

χ(K_{n}) = n = (n − 1) + 1 = d(K_{n}) + 1.

Il secondo esempio è il ciclo su un numero dispari di elementi G = C_{2k+1}. In un ciclo C tutti i vertici hanno grado due, quindi d(C) = 2.

C_{8}  C_{5}

Però un ciclo pari ha numero cromatico 2, mentre in un ciclo dispari si ha bisogno di almeno 3 colori. Quindi χ(C_{2k+1}) = 3 = d(C_{2k+1}) + 1.

3.4 Il Teorema di Brooks

Il Teorema che segue è dovuto a R.L.Brooks, che ne scrisse la dimostrazione quando era laureando presso la Cambridge University, nel 1941. Vedremo che, sotto opportune ipotesi, la limitazione per il numero cromatico dimostrato in (3.5) non è stretta, ovvero che in generale il numero cromatico raggiunge al massimo il grado del grafo, e che le sole eccezioni sono i due grafi dell’esempio nella sezione precedente.

Teorema 3.8 Sia G un grafo tale che

1. Il grado d = d(G) del grafo è strettamente superiore a due;

2. il grafo non contiene un sottografo completo su d + 1 vertici.

Allora

χ(G) ≤ d(G).

Dimostrazione. La dimostrazione di questo teorema procede per assurdo. Osserviamo che negare la tesi χ(G) ≤ d(G) vuol dire affermare che χ(G) > d(G) ma dato che vale anche la (3.5), ciò equivale a scrivere χ(G) = d(G) + 1. Supponiamo allora che esista almeno un grafo G che verifica tutte le seguenti proprietà:

1. d(G) > 2

2. K_{d(G)+1} ⊈ G

3. χ(G) = d(G) + 1

Se esiste un tale grafo, allora ne esiste uno minimale: ciò significa che tale grafo pur soddisfacendo le condizioni precedenti, non contiene nessun sottografo propriamente indotto che soddisfa a sua volta le condizioni 1. 2. e 3. Andremo ora attraverso una serie di affermazioni, valide per ogni grafo G che verifichi le condizioni 1. 2. e 3. e che sia minimale rispetto a questa proprietà: si arriverà di volta in volta a delle contraddizioni, o con le affermazioni dimostrate in precedenza, o con le ipotesi del teorema.

Affermazione 1. Per ogni x ∈ V (G) si ha

χ(G \ x) < χ(G).  (3.6)

Verifica. Qui per brevità G \ x denota il sottografo di G indotto dal sottoinsieme V (G) \ {x}. Si presentano due casi:

• d(G \ x) < d(G): allora per la (3.5) si ha

χ(G \ x) ≤ d(G \ x) + 1 < d(G) + 1 = χ(G).

• d(G \ x) = d(G): se per assurdo non fosse vera la (3.6), sarebbe

χ(G \ x) = χ(G) = d(G) + 1 = d(G \ x) + 1 :

ma questa è precisamente la condizione 3. sul grafo G \ x, il quale naturalmente verifica anche le 1. e 2., e questo contraddice la minimalità di G.

♣

Fissiamo d’ora in poi un vertice x ∈ V (G) di grado massimo d_{G}(x) = d(G) = d. Vogliamo mostrare che l’insieme di d + 1 vertici costituito da tale x e dal suo intorno induce in G un completo K_{d+1}, contro l’ipotesi 2. Per farlo, dovremo mostrare che comunque presi due vertici z, y ∈ Γ_{G}(x), allora {z, y} è un arco di G (ciò che vedremo nell’Affermazione 6.): ogni affermazione che segue, è un passo ulteriore in questa direzione. Per l’Affermazione 1. si ha χ(G\x) < χ(G): se prendiamo una colorazione f ottimale per G \ x, allora possiamo estenderla a una colorazione ottimale per G colorando il vertice x con un nuovo colore: quindi x sarà il solo vertice in G del suo colore. Inoltre per la 3. χ(G \ x) = d. Per semplicità possiamo supporre che [d] sia l’insieme dei colori, cioè f : G \ x → [d], e f(x) = d + 1. D’ora in poi, tutte le eventuali modifiche sulle colorazioni manterranno le proprietà che:

• x è l’unico vertice del suo colore;

• la colorazione è ottimale.

Chiameremo una tale colorazione x–ottimale.

Affermazione 2. Nell’intorno di x tutti i d colori della colorazione f su G \ x sono presenti. Verifica. Se così non fosse, si avrebbe |f(G \ x)| < d.

Γ_{G}(x)  ^{x}^{x_{1}}  ^{x_{2}}  ^{x_{d}}^{1}  ^{2}  ^{d}

Sia allora c ∈ [d] il colore che manca nell’intorno di x e si costruisca f′ : V (G) → [d + 1] tramite

f′(y) = \{ \begin{matrix}c & se y = x \\ f(y) & se y ≠ x \end{matrix}

Tale f′ è una nuova colorazione, poiché c ≠ f(x), ma ha meno di d+1 = χ(G) colori, impossibile. _{♣}

L’Affermazione 2. ci dice che nell’insieme Γ_{G}(x)∪{x} vi sono d+1 colori. Questa condizione è necessaria, ma non sufficiente affinché tale insieme induca un completo. Continuiamo in questa direzione. Mostreremo ora che due diversi vertici nell’intorno di x sono connessi in G\{x} (in particolare, si può trovare un cammino bicolorato che li connette). Sia Γ_{G}(x) = {x_{1}, …, x_{d}}. Possiamo identificare ogni colore con l’indice del vertice di Γ_{G}(x) su cui il colore è presente, i.e. f(x_{i}) = i per ogni i = 1, …, d. Affermazione 3. Per i ≠ j sia H_{ij} il grafo indotto in G dai vertici colorati con i e j. Allora x_{i} e x_{j} sono nella stessa componente connessa di H_{ij}. Verifica. Supponiamo per assurdo che x_{i} e x_{j} non siano nella stessa componente connessa di H_{ij}, e sia H la componente connessa di x_{i} in H_{ij}.

H  ^{x_{i}}^{f′(x_{i}) = j}  ^{x}  ^{x_{j}}^{f′(x_{j}) = j}

Si costruisca una nuova colorazione f′ su G tale che

f′(y) = \{ \begin{matrix}i & se y ∈ H e f(y) = j \\ j & se y ∈ H e f(y) = i \\ f(y) & se y ≠ H \end{matrix}

ovvero si scambino i colori i e j ma solo in H. Questo scambio dà luogo a una colorazione x–ottimale. Rispetto ad f′ però nell’intorno di x ora non appaiono tutti i colori, poiché

f′(x_{i}) = j = f(x_{j}) = f′(x_{j}),

questo contraddice l’Affermazione 2, portando all’assurdo. _{♣}

Affermazione 4. Sia C_{ij} la componente connessa di H_{ij} che contiene x_{i} e x_{j}. Allora C_{ij} è una cammino semplice. Verifica. Parlando intuitivamente: proveremo che, tentando di raggiungere x_{j} da x_{i} in C_{ij} lungo un cammino semplice, arrivati in un vertice non dovremo mai fare una scelta su come proseguire, e cioè non arriveremo mai a una “biforcazione”, il che equivale all’Affermazione. Per prima cosa, dimostriamo che il vertice x_{i} ha grado 1 in C_{ij}.

C_{ij}  ^{x}^{x_{i}}  ^{x_{j}}^{i}  ^{j}^{j} ^{j}

Osserviamo che d_{G}(x_{i}) ≤ d e da questo segue che |Γ_{G}(x_{i}) ∪ {x_{i}}| ≤ d + 1 = χ(G). Affinché il numero di colori presenti in Γ_{G}(x_{i}) ∪ {x_{i}} sia proprio il numero massimo d + 1, i suoi vertici dovrebbero avere ognuno un colore diverso. Se ci fosse una biforcazione nel punto x_{i} in C_{ij}, ci sarebbero almeno due vertici y, z ∈ Γ_{G}(x_{i}) di colore j: sia allora c il colore mancante. Potremmo così definire una nuova colorazione f′, che coincide con f salvo su x_{i}, ponendo f′(x_{i}) = c (si verifichi che in effetti tale f′ è una colorazione). La colorazione f′ così ottenuta è x–ottimale. In questo modo però in Γ_{G}(x) il colore i non appare più, e questo contraddice l’Affermazione 2. Dimostriamo ora che ogni altro vertice in V (C_{ij})\{x_{i}, x_{j}} ha grado 2 in C_{ij}. Poniamo z_{1} := x_{i} e sia z_{2} l’unico vertice di C_{ij} adiacente a x_{i}. Se z_{2} = x_{j}, non c’è più nulla da dimostrare. Se d_{C_{ij}}(z_{2}) = 2, sia z_{3} := Γ_{C_{ij}}(z_{2}) \ {z_{2}}. Costruiamo induttivamente una successione z_{1}, z_{2}, …, z_{t} di vertici di C_{ij} con Γ_{C_{ij}}(z_{i}) = {z_{i−1}} per i = 2, …, t − 1, e sia t il minimo intero tale che d_{C_{ij}}(z_{t}) > 2. Poniamo y := z_{t} e sia k il suo colore, ove k ∈ {i, j}.

C_{ij}  S^{x}^{x_{i}}  ^{y}  ^{x_{j}}^{i}  ^{j}^{\overline{k}}  ^{k}  ^{\overline{k}}^{\overline{k}}

Allora ci sono almeno tre vertici distinti colorati col colore "complementare" \overline{k} (dove \{k, \overline{k}\} = \{i, j\}); sia S l’insieme formato da questi tre vertici e da y (quindi |S| = 4). Come prima, |Γ_{G}(y) ∪ {y}| ≤ d + 1; i colori a disposizione per colorare (Γ_{G}(y) ∪ \{y\}) \ S sono (d + 1) − 3 = d − 2 (sono tutti i colori meno i tre colori k, \overline{k} e il colore di x), mentre |(Γ_{G}(y) ∪ {y}) \ S| ≤ d − 3: manca dunque almeno un colore in (Γ_{G}(y) ∪ {y}) \ S, sia esso c. A questo punto potremmo ricolorare il grafo, ponendo

f′(z) = \{ \begin{matrix}c & se z = y \\ f(z) & se z ≠ y \end{matrix}

Tale f′ è ancora una colorazione x–ottimale ma, dato che c ∉ {i, j}, avremmo sconnesso x_{i} e x_{j} nel sottografo indotto dai vertici colorati da f′ con i e j: questo contraddice l’Affermazione 3. _{♣}

Affermazione 5. Dati i, j, k distinti si ha

V (C_{ij}) ∩ V (C_{jk}) = {x_{j}},

ovvero i cammini semplici C_{ij} e C_{jk} non possono avere vertici in comune “interni” (non estremi). Verifica. Se non fosse così, allora esisterebbe un altro vertice y ≠ x_{j} con

y ∈ V (C_{ij}) ∩ V (C_{jk}).

S  ^{x}^{x_{i}}  ^{y}  ^{x_{j}}^{x_{k}}^{i}  ^{j} ^{k}^{i}  ^{j}  ^{i}^{k}_{k}

Necessariamente il colore di tale vertice è j. Esso ha due adiacenti sul cammino C_{ij} e due adiacenti sul cammino C_{jk}. Denotiamo con S l’insieme formato da questi quattro vertici e da y, dunque |S| = 5 da cui

|(Γ_{G}(y) ∪ {y}) \ S| ≤ (d + 1) − 5 = d − 4;

I colori presenti su S sono 3, precisamente {i, j, k}: il numero di colori a disposizione è pertanto d − 3, ovvero d + 1 cui si deve sottrarre il numero di colori di S più 1 per il colore attribuito ad x. Ragionando esattamente come prima, c’è un colore che non è stato utilizzato in (Γ_{G}(y) ∪ {y}) \ S col quale si può ricolorare il vertice y: per tale colorazione valgono tutte le proprietà precedenti, essendo essa x–ottimale, ma in questa nuova colorazione x_{i} e x_{j} sono sconnessi in H_{ij} arrivando ad una contraddizione con l’Affermazione 3. _{♣}

Affermazione 6. Il cammino semplice C_{ij} ha lunghezza 1, ovvero C_{ij} ha come unico arco {x_{i}, x_{j}}. Verifica. Sia per assurdo y ≠ x_{j} il vertice adiacente a x_{i} in C_{ij}. Utilizziamo a questo punto l’ipotesi 1. del Teorema, ovvero d_{G}(x) = d(G) ≥ 3: esiste un vertice x_{k} ∈ Γ_{G}(x) diverso da x_{i} e x_{j}.

C_{ij}  C_{jk} C_{ik} x x_{i}  x_{j}  x_{k} y

Definiamo una nuova colorazione del grafo scambiando i colori i e k solo in C_{ik}:

f̂(z) = \{ \begin{matrix}k & se z ∈ C_{ik} e f(z) = i \\ i & se z ∈ C_{ik} e f(z) = k \\ f(z) & se z ∉ C_{ik} \end{matrix}

La colorazione f̂ è ancora x–ottimale, quindi per essa valgono tutte le Affermazioni precedenti. Sia Ĉ_{ij} (risp. Ĉ_{jk}) la nuova componente connessa contenente x̂_{i}, x̂_{j} (rispettivamente x̂_{j}, x̂_{k}) nel sottografo di G indotto dai vertici colorati con i, j (rispettivamente j, k) nella colorazione f̂. Il vertice y appartiene a Ĉ_{jk} perché ha colore j ed è connesso al vertice x̂_{k} che è colorato da f̂ con k. Inoltre y ∈ Ĉ_{ij} perché sul cammino Ĉ_{ij} i colori non sono stati toccati: ciò dipende dal fatto, mostrato sopra, che C_{ij} ∩ C_{ik} = {x_{i}}. Dunque y ∈ Ĉ_{ij} ∩ Ĉ_{jk}, dove si è assunto y ≠ x_{j}: poiché x_{j} = x̂_{j}, questo contraddice la precedente Affermazione 5. _{♣}

Ricapitolando: nell’ipotesi per assurdo che χ(G) > d(G) abbiamo (faticosamente!) mostrato che, comunque presi due vertici dell’intorno di un vertice x di grado massimo, questi sono connessi da un arco di G, quindi il sottoinsieme di d + 1 vertici Γ_{G}(x) ∪ {x} induce un completo in G, e questo contraddice l’ipotesi 2. _{□}

3.5 Il Teorema di Erdős

Il teorema di Erdős è giustamente famoso per il metodo usato dall’autore nella sua dimostrazione. Erdős ci fa vedere l’esistenza di grafi con numero di clique e numero di stabilità esponenzialmente più piccoli del numero dei vertici, senza per questo esibirne alcuno. Il suo metodo, originariamente descritto in termini di probabilità, si chiama metodo probabilistico. In realtà, nella sua versione di base, utilizzata nella presente dimostrazione, il metodo si accontenta del conteggio di tutti i grafi con un determinato numero di vertici (qui si sceglierà 2^{k/2}), per poter concludere che il numero di quei grafi con la fissata cardinalità di vertici che non hanno la proprietà richiesta forma una minoranza rispetto al numero complessivo di grafi in questione. Questo banale principio si applica in questa dimostrazione in un modo leggermente più complicato, in quanto si calcola il numero di grafi etichettati dagli elementi di un dato insieme, e si mostra tramite un conteggio elementare che i grafi etichettati "non desiderati" rappresentano una minoranza rispetto al numero totale di grafi etichettati in questione.

Vedremo poi di provare, in modo implicito e non costruttivo, l’esistenza di grafi con numero cromatico χ(G) e numero di clique ω(G) arbitrariamente distanti. (Finora abbiamo visto solo che la disuguaglianza

χ(G) > ω(G)

è possibile, ma nient’altro.)

Teorema 3.9 Se k ≥ 4 allora esiste un grafo G con

|V (G)| ≥ 2^{\frac{k}{2}}

e tale che valgano entrambe le condizioni seguenti:

α(G) < k e ω(G) < k.

Dimostrazione. Poniamo n = 2^{\frac{k}{2}} . Denotiamo con

G_{n} := {G : V (G) = [n]}

la famiglia di tutti i grafi etichettati su n vertici. Osserviamo che

|G_{n}| = 2^{\binom{n}{2}}.

Infatti due grafi etichettati G e G′ sullo stesso insieme di vertici [n] sono distinti se E(G) ≠ E(G′); essendo E(G) ⊆ \binom{[n]}{2}, allora il numero di grafi distinti è pari alla cardinalità dell’insieme delle parti di un insieme con \binom{n}{2} elementi, cioè 2^{\binom{n}{2}}. Consideriamo anche i seguenti sottoinsiemi di G_{n}:

A_{n} := {G : G ∈ G_{n}, α(G) ≥ k}  (3.7)
Ω_{n} := {G : G ∈ G_{n}, ω(G) ≥ k}  (3.8)

Affermiamo che A_{n} e Ω_{n} non esauriscono tutti i grafi etichettati su [n], i.e.

G_{n} \ (A_{n} ∪ Ω_{n}) ≠ ∅.

Lo dimostreremo provando che |A_{n} ∪ Ω_{n}| < 2^{\binom{n}{2}}. Notiamo che

|A_{n}| = |Ω_{n}| :

l’applicazione G ↦ \overline{G} che associa ad un grafo etichettato il grafo ad esso complementare, è una biiezione di A_{n} in Ω_{n} (poiché \overline{\overline{G}} = G). Quindi, ricordando che per ogni insieme A e B vale |A ∪ B| ≤ |A| + |B| si ha:

|A_{n} ∪ Ω_{n}| ≤ |A_{n}| + |Ω_{n}| = 2|Ω_{n}|.  (3.9)

Calcoliamo ora |Ω_{n}|. Per ogni fissato K ∈ \binom{[n]}{k} raggruppiamo tutti i grafi etichettati su [n] in cui il sottografo indotto dal sottoinsieme di vertici K è completo:

Ω_{n}(K) = \{G : G ∈ G_{n}, |E(G[K])| = \binom{k}{2}\} .

Ora vale

|Ω_{n}(K)| = 2^{\binom{n}{2}−\binom{k}{2}},

dato che gli archi sul sottoinsieme K sono tutti i possibili \binom{k}{2} sottoinsiemi \{i, j\} ∈ \binom{K}{2}, e perciò la scelta degli archi per un grafo in Ω_{n}(K) si deve fare solo tra i rimanenti \binom{n}{2} − \binom{k}{2} archi possibili. Dato che se G ∈ Ω_{n} allora ω(G) ≥ k possiamo scrivere:

Ω_{n} = ⋃_{K∈\binom{[n]}{k}} Ω_{n}(K).

Quindi (si noti che l’unione non è necessariamente disgiunta):

|Ω_{n}| ≤ ∑_{K∈\binom{[n]}{k}} |Ω_{n}(K)| = \binom{n}{k}2^{\binom{n}{2}−\binom{k}{2}}.  (3.10)

Ora osserviamo che k! > 2^{k} (ma solo se k ≥ 4...) e quindi

\frac{1}{k!} < \frac{1}{2^{k}}

da cui:

\binom{n}{k} = \frac{n(n − 1) … (n − (k − 1))}{k!} < \frac{n^{k}}{k!} < \frac{n^{k}}{2^{k}} .  (3.11)

Ricordando che n = 2^{\frac{k}{2}} , si conclude che \binom{n}{k} < 2^{( \frac{k}{2} −1)k}. Infine poiché (\frac{k}{2} − 1)k < \binom{k}{2} − 1 se k > 2, possiamo dedurre

\binom{n}{k} < 2^{\binom{k}{2}−1}.  (3.12)

Mettendo insieme (3.9), (3.10) e (3.12):

|A_{n} ∪ Ω_{n}| ≤ 2 · \binom{n}{k}2^{\binom{n}{2}−\binom{k}{2}} < 2 · 2^{\binom{k}{2}−1}2^{\binom{n}{2}−\binom{k}{2}} = 2^{\binom{n}{2}},  (3.13)

implicando che |A_{n} ∪ Ω_{n}| < 2^{\binom{n}{2}}. _{□}

Applicando al grafo del Teorema di Erdős la disuguaglianza

χ(G) ≥ \frac{|V (G)|}{α(G)}

della Proposizione 3.4 e ricordando che il numero di vertici di tale G è almeno 2^{\frac{k}{2}} mentre α(G) < k, vediamo che il numero cromatico di G soddisfa la disuguaglianza

χ(G) > \frac{2^{k/2}}{k}

mentre secondo il teorema ω(G) < k. Queste disuguaglianze ci mostrano non solo che χ(G) − ω(G) può essere arbitrariamente grande, ma addirittura che il numero cromatico può essere esponenzialmente più grande del numero di clique.

Combinatoria estremale

4.1 Grafi

La combinatoria estremale si occupa delle strutture combinatorie (grafi, famiglie di sottoinsiemi di un insieme) dal punto di vista dei rapporti all’estremo tra alcuni dei loro parametri caratteristici. Come sempre, anche in questo caso, si può capire meglio di che cosa si tratta facendo un esempio. Si intuisce subito che dev’esserci una relazione tra il numero di archi e il numero cromatico di un grafo. Se un grafo non ha nessun arco, il suo numero cromatico è pari a 1. D’altra parte, se un grafo ha un arco tra ogni coppia dei suoi vertici (grafo completo), allora il suo numero cromatico è pari al suo numero di vertici. Anche se non è vero che più un grafo ha archi, più il suo numero cromatico è grande, con un po’ più di attenzione si può formulare una affermazione corretta di questo genere. Per questo motivo noi mettiamo a confronto solo grafi con lo stesso numero di vertici. Ci chiediamo qual è il massimo numero di archi che un grafo su n vertici può avere se il suo numero cromatico è strettamente inferiore a k. Se k = 2, la risposta è banale e l’abbiamo già data. Per k = 3 e oltre si deve lavorare un po’ per dare la risposta. Se denotiamo questo massimo numero di archi con U_{k}(n), allora si può mostrare che

U_{k}(n) ≥ U_{k−1}(n)

ed è in questo senso che "più un grafo ha archi, più il suo numero cromatico è grande."

La combinatoria estremale, nella sua forma autentica, non si limita però a determinare tutti i possibili rapporti tra diversi parametri caratteristici di una struttura combinatoria (in questo caso numero di archi e numero cromatico di grafi con un numero fissato di vertici), ma cerca anche di costruire tutte le configurazioni in cui si realizzano i rapporti all’estremo tra i parametri in questione. Spesso una tale struttura è unica e rappresenta una "gestione economica" di una "risorsa". (Come possiamo collegare, con il massimo numero di archi possibile, le coppie di vertici in un grafo se non lo possiamo colorare con più di due colori? Anche in questo caso si può verificare, pure se noi non lo faremo, che i grafi che hanno il massimo numero possibile di archi per n vertici e numero cromatico due, sono tutti isomorfi.) Molte strutture esistenti nella natura sono realizzazioni di una tale gestione economica di qualche risorsa. L’esempio più in vista di questo fenomeno è la sfera. Si può dimostrare (ma questo è già geometria, e non fa parte di questo corso), che tra tutti i solidi tridimensionali che hanno lo stesso volume, la sfera ha la superficie più piccola. Ecco perché i cactus nel deserto hanno spesso una forma sferica: in questo modo si minimizza l’evaporazione dell’acqua, risorsa preziosa per una pianta nel deserto.

Osservazione. Non difficile mostrare che U_{3}(n) ≤ \frac{n^{2}}{4} . Infatti un grafo G su n vertici bicolorabile è un sottografo del bipartito completo K_{x,n−x} con 1 < x < n, dunque |E(G)| ≤ x(n − x): al variare di x ∈ [1, n − 1] ∩ ℕ, il polinomio x(n − x) ha valore massimo in x = \frac{n}{2} se n è pari, in x = ⌊\frac{n}{2}⌋ se n è dispari: in entrambi i casi |E(G)| ≤ \frac{n^{2}}{4} .

Ricordando la caratterizzazione dei grafi bipartiti della Proposizione 3.3, U_{3}(n) è il massimo numero di archi in un grafo con n vertici e senza cicli dispari. Denotiamo ora con T_{3}(n) il massimo numero di archi in un grafo con n vertici che non contiene triangoli (ma che può contenere cicli dispari più lunghi): vedremo ora che il nuovo vincolo, più debole, non permette un maggior numero di archi.

Teorema 4.1 (Mantel-Turán) Sia

G_{n} = {G : |V (G)| = n, K_{3} ⊈ G}

la famiglia dei grafi su n vertici che non contengono triangoli: allora

T_{3}(n) = max\{|E(G)| : G ∈ G_{n}\} ≤ \frac{n^{2}}{4} .

Dimostrazione. Se {a, b} ∈ E(G) allora nessun altro vertice può essere adiacente contemporaneamente ad a e a b, i.e. Γ(a)∩Γ(b) = ∅, in quanto se fosse c ∈ Γ(a)∩Γ(b) l’insieme {a, b, c} indurrebbe un completo K_{3} in G.

a c b

Questo implica che per ogni {a, b} ∈ E(G) si ha:

|Γ(a)| + |Γ(b)| = |Γ(a) ∪ Γ(b)| ≤ |V (G)| = n

ovvero

d_{G}(a) + d_{G}(b) ≤ n per ogni {a, b} ∈ E(G).

Sommando la precedente disequazione su tutti gli archi del grafo si ottiene

∑_{{a,b}∈E(G)}[d_{G}(a) + d_{G}(b)] ≤ n|E(G)|  (4.1)

Si noti che nella sommatoria precedente il termine d_{G}(a) compare in abbinamento con tutti i vertici b adiacenti ad a, per un totale di d_{G}(a) volte e quindi

∑_{{a,b}∈E(G)} (d_{G}(a) + d_{G}(b)) = ∑_{x∈V (G)} d_{G}(x)^{2}  (4.2)

Facciamo una breve digressione. Ricordiamo che una funzione f : ℝ → ℝ si dice convessa se per ogni 0 ≤ t ≤ 1 e per ogni x_{1}, x_{2} nel dominio di definizione della funzione f si ha:

tf(x_{1}) + (1 − t)f(x_{2}) ≥ f(tx_{1} + (1 − t)x_{2})  (4.3)

ovvero il segmento di estremi (x_{1}, f(x_{1})) e (x_{2}, f(x_{2})) si trova al di sopra dell’arco della curva y = f(x) avente gli stessi estremi.

x_{1}  y_{1} y_{2}  x_{2}  y = f(x)

Per una funzione convessa vale la disuguaglianza di Jensen, che generalizza la (4.3): comunque presi k valori x_{1}, …, x_{k} nel dominio di definizione della f e k scalari non negativi α_{1}, …, α_{k} tali che ∑_{i=1}^{k} α_{i} = 1 si ha

∑_{i=1}^{k} α_{i}f(x_{i}) ≥ f(∑_{i=1}^{k} α_{i}x_{i}).  (4.4)

Il valore ∑_{i=1}^{k} α_{i}x_{i} si chiama combinazione convessa degli x_{i}. Nel nostro caso la funzione convessa in questione è l’elevamento a quadrato; in particolare se prendiamo k = |V (G)| = n e α_{i} = \frac{1}{n} per i = 1, …, n, usando la (4.4) in (4.2) possiamo scrivere

∑_{x∈V (G)}(d_{G}(x))^{2} = \frac{n}{n} ∑_{x∈V (G)}(d_{G}(x))^{2} ≥ n (\frac{∑_{x∈V (G)} d_{G}(x)}{n})^{2} ;

a questo punto sostituendo qui sopra ∑_{x∈V (G)} d_{G}(x) = 2|E(G)| e ricordando la (4.1) e la (4.2) si ottiene che

n|E(G)| ≥ ∑_{x∈V (G)}(d_{G}(x))^{2} ≥ n (\frac{2|E(G)|}{n})^{2}

da cui

n ≥ \frac{4|E(G)|}{n}

ed infine

|E(G)| ≤ \frac{n^{2}}{4} .

□

Il Teorema di Mantel–Turán nella forma qui presentata ci dice che T_{3}(n) ≤ \frac{n^{2}}{4} . Osserviamo che se n è pari allora T_{3}(n) = \frac{n^{2}}{4} , poiché un grafo su un numero pari di vertici, con una bipartizione dei vertici in due insiemi stabili con \frac{n}{2} vertici in ciascuno di essi e che abbia tutti gli archi tra vertici di classi diverse, ha esattamente questo numero di archi. Se n è dispari, questa costruzione non esiste. Anche in questo caso si può determinare T_{3}(n). Il “vero” Teorema di Mantel–Turán dice che

T_{3}(n) = ⌊\frac{n}{2}⌋ ⌈\frac{n}{2}⌉ .

4.2 Famiglie di insiemi ovvero ipergrafi

Sia F una famiglia di sottoinsiemi di [n]. Diremo che F è una famiglia di Sperner se comunque presi due sottoinsiemi distinti della famiglia, essi non si contengono, ovvero

\{E, E′\} ∈ \binom{F}{2} ⇒ E ⊈ E′.

La struttura combinatoria definita, in analogia con i grafi, tramite un insieme di base V e una famiglia F dei suoi sottoinsiemi, spesso si chiama ipergrafo. Difatti, mentre un ipergrafo si definisce come una coppia (V, F) con F ⊆ 2^{V}, un grafo semplice è definito come una coppia (V, F) con F ⊆ \binom{V}{2}. Notando che \binom{V}{2} ⊆ 2^{V}, ci si rende conto che gli ipergrafi costituiscono una generalizzazione del concetto di grafo. Ad esempio, la famiglia di tutti i sottoinsiemi di vertici che inducono una clique in un fissato grafo, definisce un ipergrafo sullo stesso insieme di vertici. Inoltre la famiglia, più ristretta, di quegli insiemi che inducono una clique massimale, forma una famiglia di Sperner. È interessante chiedersi quanti membri può avere una tale famiglia. Per risolvere questo quesito, ci serviamo di una disuguaglianza, che a questo punto sembrerebbe priva di significato proprio.

Per una famiglia di Sperner vale la seguente disuguaglianza, nota con il nome di disuguaglianza LYM (dai nomi di Lubell, Yamamoto, Meshalkin, cfr. [7]).

Proposizione 4.2 Se F è una famiglia di Sperner di [n] allora

∑_{E∈F} \binom{n}{|E|}^{−1} ≤ 1  (4.5)

Dimostrazione. Definiamo catena in [n] una successione di sottoinsiemi di [n] tali che

∅ = D_{0} ⊂ D_{1} ⊂ D_{2} ⊂ … ⊂ D_{n} = [n]

ove |D_{i}| = i. Posto x_{i} = D_{i} \ D_{i−1} per i = 1, …, n, è chiaro che ogni catena determina una permutazione x_{1}x_{2} … x_{n} degli elementi di [n] e viceversa: ne segue che il numero di catene è n!. Diremo che una catena D_{0} ⊂ … ⊂ D_{n} di [n] passa per il sottoinsieme E ⊆ [n] se D_{|E|} = E. Associamo ora ad ogni elemento E ∈ F della famiglia di Sperner l’insieme delle catene di [n] che passano per esso:

D_{E} = {D_{0} ⊂ … ⊂ D_{n} : D_{|E|} = E}.

Si osservi che se una catena passa per E allora essa non passa per nessun altro sottoinsieme E′ in F: infatti se una catena passasse sia per E che per E′ allora si avrebbe ad esempio che E ⊂ E′ (oppure E′ ⊂ E). Da questo deriva

∑_{E∈F} |D_{E}| ≤ n!  (4.6)

perché, essendo D_{E} ∩ D_{E′} = ∅ se E ≠ E′, ogni catena nella sommatoria viene considerata al più una volta. Ora affermiamo che il numero di catene che passano per un fissato insieme E è

|D_{E}| = |E|!(n − |E|)!  (4.7)

Infatti affinché una catena passi per l’insieme E si deve poter arrivare ad esso, ed il numero di modi in cui ciò può avvenire è pari al numero di tutte le permutazioni degli elementi di E, cioè |E|!. Giunti ad E si completa la catena "allargando" E, ovvero aggiungendo in ordine arbitrario i restanti elementi di [n] \ E: ciò può avvenire in (n − |E|)! modi. Mettendo insieme (4.6) e (4.7) si ottiene:

∑_{E∈F} |E|!(n − |E|)! ≤ n!

e dividendo ambo i membri per n!

∑_{E∈F} \frac{|E|!(n − |E|)!}{n!} = ∑_{E∈F} \binom{n}{|E|}^{−1} ≤ 1.

□

Teorema 4.3 La massima cardinalità M(n) di una famiglia di sottoinsiemi di [n] che gode della proprietà di Sperner è

M(n) = \binom{n}{⌊\frac{n}{2}⌋} = \binom{n}{⌈\frac{n}{2}⌉}  (4.8)

Dimostrazione. Sia F = \binom{[n]}{k} la famiglia di tutti i sottoinsiemi di [n] con k elementi. Tale famiglia è di Sperner, in quanto insiemi distinti ma con la stessa cardinalità non si possono contenere. Abbiamo allora costruito per ogni k una famiglia di Sperner di cardinalità \binom{n}{k}. Da questo segue che

M(n) ≥ \binom{n}{k}

per k = 1, …, n. In particolare per k = ⌊\frac{n}{2}⌋ si ha

M(n) ≥ \binom{n}{⌊\frac{n}{2}⌋}.  (4.9)

Sia ora F una famiglia di Sperner qualunque. Per ottenere un limite superiore per M(n) usiamo la disuguaglianza LYM. Abbiamo visto in (2.19) che, fissato n, il coefficiente binomiale \binom{n}{k} raggiunge il massimo per k = ⌊\frac{n}{2}⌋:

\binom{n}{k} ≤ \binom{n}{⌊\frac{n}{2}⌋},

e passando ai reciproci

\binom{n}{k}^{−1} ≥ \binom{n}{⌊\frac{n}{2}⌋}^{−1} per ogni k.

Utilizzando la precedente disuguaglianza nella (4.5) si ricava

1 ≥ ∑_{E∈F} \binom{n}{|E|}^{−1} ≥ ∑_{E∈F} \binom{n}{⌊\frac{n}{2}⌋}^{−1} = \binom{n}{⌊\frac{n}{2}⌋}^{−1} ∑_{E∈F} 1 = |F|\binom{n}{⌊\frac{n}{2}⌋}^{−1}, (4.10)

e moltiplicando per \binom{n}{⌊\frac{n}{2}⌋} si deduce

|F| ≤ \binom{n}{⌊\frac{n}{2}⌋} per ogni F;  (4.11)

passando al massimo su tutte le famiglie di Sperner, si ottiene allora

M(n) ≤ \binom{n}{⌊\frac{n}{2}⌋}.  (4.12)

Confrontando (4.9) con (4.12) si ottiene (4.8) _{□}

Osservazione. Si noti che quando n è pari vi è un’unica famiglia di Sperner di massima cardinalità. Infatti l’unico modo di avere l’uguaglianza in (4.10) è di avere

|E| = \frac{n}{2} per ogni E ∈ F

quindi F ⊆ \binom{[n]}{\frac{n}{2}} e dato che |F| = \binom{n}{\frac{n}{2}}, si deve avere F = \binom{[n]}{\frac{n}{2}}. Nel caso di n dispari, ci sono due famiglie complementari che, ambedue, raggiungono la massima cardinalità, ma la dimostrazione che non ve ne siano altre è molto più complicata. Si noti però che lo stesso Sperner in [13] ha mostrato proprio questo.

Diciamo che una famiglia F ⊆ 2^{[n]} di sottoinsiemi di [n] è una famiglia intersecante se

\{E, E′\} ∈ \binom{F}{2} ⇒ E ∩ E′ ≠ ∅.  (4.13)

Proposizione 4.4

max{|F| : F ⊆ 2^{[n]}, F intersecante } = 2^{n−1}.

Dimostrazione. Anzitutto, consideriamo la seguente famiglia di sottoinsiemi di [n]

{A ∪ {n} : A ⊆ [n − 1]} :

questa è una famiglia intersecante poiché comunque presi due suoi elementi distinti, essi si intersecano almeno nell’elemento n, e contiene 2^{n−1} sottoinsiemi, pertanto

max{|F| : F ⊆ 2^{[n]} intersecante } ≥ 2^{n−1}.

Per avere l’altro verso della disuguaglianza, partizioniamo tutti i sottoinsiemi di [n] tramite la relazione di equivalenza ρ definita da

AρB ⇔ B = Ā.

Ogni classe di equivalenza è composta da una coppia di sottoinsiemi (A, Ā); vi sono quindi \frac{2^{n}}{2} = 2^{n−1} classi per la relazione ρ. Osserviamo ora che una famiglia intersecante può contenere al più un membro di ogni classe, essendo A ∩ Ā = ∅. Si ottiene allora |F| ≤ 2^{n−1} per ogni famiglia intersecante F e passando al massimo si deduce che

max{|F| : F ⊆ 2^{[n]} intersecante } ≤ 2^{n−1}._{□}

Supponiamo ora di avere a disposizione un insieme universo U. Prendiamo in U una famiglia Σ di sottoinsiemi di U, che possiamo pensare come i gruppi di campionamento per un determinato sondaggio da eseguire in U. Denotiamo con C ⊆ U un fissato sottoinsieme di elementi di U. Sempre in questa metafora del sondaggio, vediamo C come una particolare categoria di persone, che rispondono a determinati requisiti all’interno dell’universo U. Vorremmo capire quali proprietà devono soddisfare le famiglie di sondaggio per essere “buone” nel senso che segue. La quantità \frac{|C∩S|}{|S|} misura la “densità” di C relativamente al sottoinsieme S ∈ Σ. Nell’ipotesi in cui per un valore λ e per ogni S ∈ Σ si abbia

\frac{|C ∩ S|}{|S|} ≤ λ  (4.14)

si vorrebbe concludere che anche la densità globale di C rispetto all’universo U soddisfa la stessa limitazione

\frac{|C|}{|U|} ≤ λ  (4.15)

Diciamo che Σ ⊆ 2^{U} è una famiglia di sondaggio per U se ogni x ∈ U è ricoperto dallo stesso numero di elementi di Σ, ovvero se la cardinalità dell’insieme {S ∈ Σ : x ∈ S} non dipende dalla particolare scelta di x ma esiste una costante c ∈ ℕ tale che per ogni x si ha

|{S ∈ Σ : x ∈ S}| = c.  (4.16)

Queste sono le famiglie “buone” come vediamo nella seguente:

Proposizione 4.5 Sia Σ una famiglia di sondaggio per U e sia λ ∈ ℝ. Allora

\frac{|C ∩ S|}{|S|} ≤ λ per ogni S ∈ Σ ⇒ \frac{|C|}{|U|} ≤ λ  (4.17)

Dimostrazione. Per la (4.16) si ha che

∑_{S∈Σ} |S| = c|U|

e anche

∑_{S∈Σ} |C ∩ S| = c|C|

D’altra parte per l’ipotesi (4.14) vale

∑_{S∈Σ} |C ∩ S| ≤ λ ∑_{S∈Σ} |S|

ovvero

c|C| ≤ λc|U|

che equivale a

\frac{|C|}{|U|} ≤ λ.

□

Abbiamo visto nella Proposizione 4.4 qual è il massimo raggiunto dalla cardinalità di una qualunque famiglia intersecante di [n]. Vediamo ora cosa succede nel caso in cui la famiglia sia uniforme, ovvero i suoi insiemi abbiano tutti la stessa cardinalità.

Teorema 4.6 (Erdős-Ko-Rado) Sia

I(n, k) = max \{|F| : F ⊆ \binom{[n]}{k}, F intersecante\}

allora

I(n, k) = \{ \begin{matrix}\binom{n−1}{k−1} & k ≤ \frac{n}{2} \\ \binom{n}{k} & k > \frac{n}{2} \end{matrix}

Dimostrazione. Se k > \frac{n}{2}, allora in [n] non c’è spazio sufficiente per due sottoinsiemi di cardinalità k a intersezione vuota, quindi senz’altro \binom{[n]}{k} è una famiglia intersecante ed ha la massima cardinalità possibile, quindi

I(n, k) = \binom{n}{k} per k > \frac{n}{2}.

Dimostriamo ora che k ≤ \frac{n}{2} implica I(n, k) = \binom{n−1}{k−1}. Analogamente a quanto visto nella dimostrazione della Proposizione 4.4, se poniamo

E = \{A ∪ \{n\} : A ∈ \binom{[n − 1]}{k − 1}\} ,

la famiglia E ⊆ \binom{[n]}{k} è intersecante, uniforme, e contiene \binom{n−1}{k−1} elementi: pertanto

I(n, k) ≥ \binom{n − 1}{k − 1}.  (4.18)

Per l’altro verso della disequazione usiamo il principio di sondaggio. Nel ruolo di insieme universo consideriamo U = \binom{[n]}{k}, il ruolo di C sarà svolto da una qualunque famiglia intersecante F con insiemi di cardinalità k. Chi sarà il gruppo dei campioni Σ per il sondaggio? Sia Π l’insieme delle configurazioni cicliche di [n], che possiamo pensare come le permutazioni di [n] che si decompongono in un unico ciclo lungo n. Per ogni fissato π ∈ Π, diremo che A ∈ \binom{[n]}{k} è un "intervallo ciclico" della configurazione ciclica π se gli elementi di A si trovano consecutivamente sul ciclo, ovvero se esiste un indice l ∈ [n] tale che A = {l, π(l), π^{2}(l), …, π^{k−1}(l)}. Sia ora S(π) l’insieme di tali intervalli ciclici di π. Ad esempio, per n = 8, k = 3 e π = (1, 3, 6, 7, 5, 2, 4, 8) si ha

S(π) = {[1, 3, 6]; [3, 6, 7]; [6, 7, 5]; [7, 5, 2]; [5, 2, 4]; [2, 4, 8]; [4, 8, 1]; [8, 1, 3]}.

2 4  8  1 3 6 7 5  π

Poniamo infine

Σ := {S(π) : π ∈ Π} .  (4.19)

Affermiamo che Σ è una famiglia di sondaggio per U: infatti la condizione (4.16) è verificata in quanto, fissati comunque due elementi distinti A, A′ di U, si ha per simmetria che

|{π ∈ Π : A intervallo ciclico di S(π)}| = |{π ∈ Π : A′ intervallo ciclico di S(π)}|.

Ci resta da dimostrare che per una famiglia intersecante F di \binom{[n]}{k} vale

|F| ≤ \binom{n − 1}{k − 1};  (4.20)

da questa disuguaglianza, passando al massimo, dato che la famiglia F è arbitraria, si otterrà

I(n, k) ≤ \binom{n − 1}{k − 1}.  (4.21)

Osserviamo che, essendo |U| = \binom{n}{k} e

\begin{matrix}( & {n−1 \atop k−1} & ) \\ ( & {n \atop k} & ) \end{matrix} = \frac{k}{n},

la disuguaglianza (4.20) è equivalente alla disuguaglianza

\frac{|F|}{|U|} ≤ \frac{k}{n}.  (4.22)

Fissato π ∈ Π vogliamo valutare la densità degli elementi della famiglia F in ogni gruppo di sondaggio S(π). Naturalmente |S(π)| = n mentre, come vedremo,

|F ∩ S(π)| ≤ k.  (4.23)

Dimostriamo quest’ultima affermazione, che è senz’altro vera se F ∩ S(π) = ∅. Se F ∩ S(π) ≠ ∅, possiamo identificare ogni suo elemento con una k–upla ordinata secondo il verso della permutazione ciclica π. Sia allora

A = [a_{1}, a_{2}, …, a_{k}] ∈ F ∩ S(π).

Denotiamo inoltre con [ · , a_{i}] l’intervallo ciclico di S(π) che finisce in a_{i} e con [a_{i}, ·] l’intervallo ciclico di S(π) che inizia in a_{i}. Poiché F è intersecante, ogni altro insieme B ∈ F deve intersecare A in uno dei suoi elementi a_{j}. Inoltre se B ∈ F ∩ S(π), allora B è anche uno degli intervalli ciclici di π che iniziano o finiscono in uno degli elementi a_{j} ∈ A. Elenchiamo qui tutti questi intervalli ciclici, accoppiandoli a due a due come segue:

[ · , a_{1}] [a_{2}, · ]

[ · , a_{2}] [a_{3}, · ]

⋮ ⋮

[ · , a_{k−1}] [a_{k}, · ]

[ · , a_{k}]

Si noti che l’ultimo intervallo della lista non è stato "accoppiato" poiché, essendo k ≤ \frac{n}{2}, l’intervallo ciclico che comincia nell’elemento successivo ad a_{k} in π non interseca A. Inoltre nella lista ci sono esattamente 2k − 1 intervalli ciclici di S(π). Infine i due intervalli su ogni riga della lista sono disgiunti tra loro, in quanto k ≤ \frac{n}{2}: pertanto [ · , a_{k}] = A e ogni eventuale altro insieme B ∈ F ∩S(π) diverso da A può essere solo uno dei due intervalli su ciascuna delle prime k − 1 righe. Concludendo, da (4.23) segue che per ogni π ∈ Π, la densità di F in S(π) è limitata da:

\frac{|F ∩ S(π)|}{|S(π)|} ≤ \frac{k}{n}

e poiché Σ è una famiglia di sondaggio, possiamo applicare la (4.17) al nostro caso, deducendo allora la (4.22). _{□} 68 CAPITOLO 4. COMBINATORIA ESTREMALE

Tecniche di conteggio

5.1 Il principio di inclusione–esclusione

Il teorema che segue è una generalizzazione della familiare identità

|A ∪ B| = |A| + |B| − |A ∩ B|.

In quanto segue, si adotta l’usuale convenzione che l’intersezione dei membri (inesistenti!) di una famiglia vuota di sottoinsiemi di un fissato insieme X è l’insieme X stesso.

Teorema 5.1 Sia X un insieme finito e siano F_{1}, F_{2}, …, F_{r} sottoinsiemi di X non necessariamente distinti. Il numero N degli elementi di X che non appartengono a nessuno dei sottoinsiemi F_{i}, i ∈ [r], soddisfa la formula

N = |X \ ∪_{i∈[r]}F_{i}| = |X| + ∑_{∅≠E⊆[r]}(−1)^{|E|}| ∩_{i∈E} F_{i}| = ∑_{E⊆[r]}(−1)^{|E|}| ∩_{i∈E} F_{i}| (5.1)

Dimostrazione. Per un fissato sottoinsieme F ∈ 2^{X}, si chiama funzione caratteristica dell’insieme F la funzione χ(·, F) : X → {0, 1} definita da:

χ(x, F) = \{ \begin{matrix}1 & x ∈ F \\ 0 & x ∉ F \end{matrix}

Con questa notazione, la cardinalità di un insieme F risulta essere

|F | = ∑_{x∈X} χ(x, F).

Interpreteremo χ(x, F) come il “contributo” di x alla cardinalità di F: tale contributo è 0 o 1 a seconda che x appartenga o meno a F. Con questa notazione, possiamo esprimere N come

N = ∑_{x∈X} χ(x, X \ ∪_{i∈[r]}F_{i})  (5.2)

Per verificare l’enunciato, fissiamo per il momento un arbitrario elemento x ∈ X e analizziamo nei dettagli il contributo χ(x, X \ ∪_{i∈[r]}F_{i}) di x al membro destro della (5.1). Poiché si ha

∑_{E⊆[r]}(−1)^{|E|}| ∩_{i∈E} F_{i}| = ∑_{E⊆[r]}(−1)^{|E|} ∑_{x∈X} χ(x, ∩_{i∈E}F_{i})
= ∑_{x∈X} ∑_{E⊆[r]}(−1)^{|E|}χ(x, ∩_{i∈E}F_{i}),  (5.3)

alla luce di (5.2) è sufficiente dimostrare per ogni x ∈ X che

χ(x, X \ ∪_{i∈[r]}F_{i}) = ∑_{E⊆[r]}(−1)^{|E|}χ(x, ∩_{i∈E}F_{i}).  (5.4)

A tal fine, denotiamo con D(x) ⊆ [r] l’insieme degli indici i per cui x ∈ F_{i}. In altre parole, noi abbiamo χ(x, ∩_{i∈E}F_{i}) = 1 se e solo se E ⊆ D(x). Ciò significa che il contributo "cumulativo" effettivo ∑_{E⊆[r]}(−1)^{|E|}χ(x, ∩_{i∈E}F_{i}) di x al membro destro di (5.4) è uguale a

∑_{E⊆D(x)}(−1)^{|E|}χ(x, ∩_{i∈E}F_{i}).

A questo punto osserviamo che vale, in generale, la relazione

χ(x, ∩_{i∈E}F_{i}) = ∏_{i∈E} χ(x, F_{i}).

Utilizzando questa formula, il contributo alla nostra sommatoria di un elemento x appartenente esattamente a quegli insiemi F_{i} il cui indice i è in D(x) può essere riscritto come

∑_{E⊆D(x)}(−1)^{|E|}χ(x, ∩_{i∈E}F_{i}) = ∑_{E⊆D(x)}(−1)^{|E|} ∏_{i∈E} χ(x, F_{i}) = ∑_{E⊆D(x)}(−1)^{|E|} (5.5)

D’altra parte, notiamo che per un qualunque sottoinsieme D si ha

∑_{E⊆D}(−1)^{|E|} = ∑_{j=0}^{|D|} ∑_{E∈\binom{D}{j}}(−1)^{j}

= ∑_{j=0}^{|D|}(−1)^{j} |\binom{D}{j}|

= ∑_{j=0}^{|D|}(−1)^{j}\binom{|D|}{j}

= (1 − 1)^{|D|}

dove l’ultima relazione è lo sviluppo della potenza del binomio. Quest’ultima espressione è quindi uguale a 1 se e solo se D è l’insieme vuoto, mentre è uguale a 0 in ogni altro caso. Pertanto per D = D(x) la (5.5) è pari ad 1 esattamente quando x non è contenuto in nessuno degli insiemi F_{i}. Ciò significa che

∑_{E⊆D(x)}(−1)^{|E|} = 0^{|D(x)|} = χ(x, X \ ∪_{i∈[r]}F_{i})  (5.6)

da cui segue la relazione (5.4). □

5.2 Applicazioni

Se consideriamo l’insieme [r] come un insieme di proprietà di cui i vari elementi di X possono godere, allora F_{i} va pensato come l’insieme di quegli elementi di X che posseggono la proprietà i e in questa interpretazione N è il numero degli elementi di X che non posseggono nessuna delle proprietà in [r].

Una delle più importanti applicazioni della formula di inclusione–esclusione riguarda il conteggio dei numeri naturali coprimi con un fissato naturale n, ovvero dei numeri naturali k con 1 ≤ k ≤ n tali che il massimo comune divisore (k, n) tra k ed n è 1. Denotiamo questa funzione enumerativa con

ϕ(n) = |{k; k ∈ [n], (k, n) = 1}| :

essa viene chiamata funzione di Euler. Otteniamo subito dalla formula di inclusione– esclusione il seguente risultato:

Teorema 5.2 Sia {p_{1}, …, p_{r}} l’insieme dei divisori primi di n (quindi la fattorizzazione in primi di n è n = p_{1}^{α_{1}} ⋯ p_{r}^{α_{r}}, con α_{i} > 0.) Allora

ϕ(n) = n ∏_{i=1}^{r} (1 − \frac{1}{p_{i}} ) .  (5.7)

Dimostrazione. Notiamo che se d è un arbitrario divisore di n, allora il numero dei multipli di d che appartengono ad [n] è pari a \frac{n}{d}. Infatti, sia n = dm: i multipli di d in [n] sono i numeri d, 2d, 3d, …, md con m = \frac{n}{d}, come affermato. Adesso diciamo che un numero k ∈ [n] ha la i–esima proprietà se k è divisibile per p_{i}. Osserviamo che (k, n) = 1 se e solo se k non è un multiplo di nessuno dei divisori primi p_{i} di n, cioè se k non soddisfa la i–sima proprietà per nessun i ∈ [r], o equivalentemente se k ∈ [n]\∪_{i∈[r]}F_{i}; inoltre se E ⊆ [r], allora k è multiplo di tutti i primi p_{i} con i ∈ E se e solo se k è multiplo del loro prodotto ∏_{i∈E} p_{i}. Da questo e per quanto detto all’inizio si deduce che

| ∩_{i∈E} F_{i}| = \frac{n}{∏_{i∈E} p_{i}};

quindi adattando la formula (5.1) dell’inclusione–esclusione al nostro caso possiamo scrivere

ϕ(n) = ∑_{E⊆[r]}(−1)^{|E|} \frac{n}{∏_{i∈E} p_{i}} = n ∑_{E⊆[r]}(−1)^{|E|} \frac{1}{∏_{i∈E} p_{i}} .

Il lettore verifichi che, per la proprietà distributiva del prodotto, si ha

∑_{E⊆[r]}(−1)^{|E|} \frac{1}{∏_{i∈E} p_{i}} = ∏_{i=1}^{r} (1 − \frac{1}{p_{i}} )

e da questo si ottiene la relazione cercata (5.7). □

Un’altra ben nota applicazione del principio di inclusione–esclusione ci fornisce una bella e sorprendente formula asintotica per il numero delle permutazioni senza punti fissi, che qui vogliamo chiamare "permutazioni sconvolgenti" (in inglese: derangements). Per introdurre questo argomento ricorreremo al concetto intuitivo (ma qui non matematizzato, visto che l’argomento non è stato ancora studiato dal nostro lettore) delle probabilità. Immaginate che in una grande tintoria informatizzata si rompa il calcolatore e, di conseguenza, il gestore reinventi un’etichettatura dei clienti (assegnazione dei pacchi pronti alla consegna ai diversi clienti) completamente casuale. Qual è la "probabilità" che nessun pacco arrivi correttamente a destinazione? Si ha la tentazione di dire che, se ci sono molti clienti, questa probabilità è in pratica trascurabile (molto vicina allo 0). Ebbene, non è così. Infatti questa probabilità è più elevata (addirittura del doppio) di quella di ottenere un fatidico 6 lanciando un dado di gioco.

Diremo che una permutazione f : [n] → [n] è sconvolgente se f(i) ≠ i per ogni i ∈ [n]. Sia s(n) il numero di tali permutazioni.

Per ottenere una stima di quante sono le permutazioni sconvolgenti, traduciamo nelle notazioni della formula di inclusione–esclusione gli oggetti in esame. Sia X l’insieme delle permutazioni di [n]. Diremo che una permutazione f ∈ X possiede la proprietà i se f(i) = i. Dunque una permutazione è sconvolgente se f non soddisfa nessuna delle proprietà i, per i ∈ [n], ovvero se f ∈ X \ ∪_{i=1}^{n}F_{i}. Fissato un sottoinsieme E di [n], le permutazioni che invece soddisfano tutte le proprietà i con i ∈ E (cioè gli elementi di ∩_{i∈E}F_{i}) sono quelle per le quali tutti gli elementi di E sono punti fissi, e queste permutazioni si possono identificare con le (n − |E|)! permutazioni (qualunque) sugli elementi di [n] \ E. Usando il principio di inclusione-esclusione si può calcolare il numero s(n) di permutazioni sconvolgenti

s(n) = ∑_{E⊆[n]}(−1)^{|E|}(n − |E|)!

= ∑_{j=0}^{n} ∑_{E∈\binom{[n]}{j}}(−1)^{|E|}(n − |E|)!

= ∑_{j=0}^{n}(−1)^{j}(n − j)!\binom{n}{j}

= n! ∑_{j=0}^{n} \frac{(−1)^{j}}{j!}  (5.8)

Ricordiamo la relazione

e = lim_{n→∞} ∑_{j=0}^{n} \frac{1}{j!}

dove e ∼ 2, 718 è la base del logaritmo naturale, da cui si ottiene

lim_{n→∞} ∑_{j=0}^{n} \frac{(−1)^{j}}{j!} = \frac{1}{e}.  (5.9)

Da questo, poiché la proporzione di permutazioni sconvolgenti di [n] rispetto alla totalità di permutazioni di [n] è data dal rapporto

\frac{s(n)}{n!}

da (5.8) e (5.9) segue che

lim_{n→∞} \frac{s(n)}{n!} = \frac{1}{e}

e quindi asintoticamente

\frac{s(n)}{n!} ∼ \frac{1}{e} > \frac{1}{3}.

□

In effetti, non è difficile mostrare che il numero di permutazioni senza punti fissi su [n] è proprio uguale all’intero più vicino a n!/e.

74 CAPITOLO 5. TECNICHE DI CONTEGGIO

Bibliografia

[1] P. J. Cameron: Combinatorics. Topics, techniques, algorithms. Cambridge University Press, Cambridge (1994).

[2] P. Erdős: Some remarks on the theory of graphs. Bulletin of the American Mathematical Society 53, 292–294 (1947).

[3] P. Erdős, Chao Ko, R. Rado: Intersection theorems for systems of finite sets. Quarterly Journal of Mathematics Oxford Series (2) 12, 313–320 (1961).

[4] G.O.H. Katona: Extremal problems for hypergraphs. in: Combinatorics, Part 2 Proceedings of NATO Advanced Study Institute, Breukelen 13–42 (1974).

[5] J. B. Kruskal: On the shortest spanning subtree of a graph and the traveling Salesman problem. Proceedings of the American Mathematical Society 7, 48–50 (1956).

[6] L. Lovász: Combinatorial Problems and Exercises, 2nd edition. Akadémiai Kiadó, Budapest and North–Holland, Amsterdam (1993).

[7] D. Lubell: A short proof of Sperner’s lemma. Journal of Combinatorial Theory 1 p. 299 (1966).

[8] J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics. Clarendon Press. Oxford (1998).

[9] L. D. Meshalkin: A generalization of Sperner’s lemma on the number of subsets of a finite set. (English translation), Theory of Probabability and its Applications 8, 204–205 (1964).

[10] J. Moon: Various proofs of Cayley’s formula for counting trees. Chapter 11 in A Seminar on Graph Theory (F. Harary ed.) Holt Rinehart and Winston, New York, 70–78 (1967).

[11] H. Prüfer: Neuer Beweis eines Satzes über Permutationen. Archiv der Mathematik und Physik. (3) 27, 142–144 (1918).

[12] B. Reed: A strengthening of Brooks’ Theorem. Journal of Combinatorial Theory, Series B 76, n. 2, 136–149 (1999).

[13] E. Sperner: Ein Satz über Untermengen einer endlichen Menge. Mathematische Zeitschrift vol. 27, 544–548 (1928).

[14] J. H. van Lint, R. M. Wilson: A Course in Combinatorics. Cambridge University Press. Cambridge (1992).

[15] K. Yamamoto: Logarithmic order of free distributive lattices. Journal of the Mathematical Society of Japan 6, 343–353 (1954).