In this talk we will discuss the problem of providing "uniform growth schemes" for various types of planar maps — namely, of coupling a uniform map with n faces with a uniform map with n+1 faces in such a way that the smaller map is always obtained from the larger by collapsing a single face. We will explore the connection of this question to the idea of growing trees by the leaves and briefly touch on some applications: on one side, some implications for mixing time questions for edge flip chains, and on the other, some results about where the Brownian tree naturally grows leaves. Based on joint works with Alexandre Stauffer, and with Nicolas Curien and Robin Stephenson.
Complementi di Matematica – Induzione transfinita
Induzione transfinita. Data una proprietà , se per ogni ordinale
si ha
se per ogni ordinale vale
allora vale
allora la proprietà vale per tutti gli ordinali.
Esercizi
- Costruire una base di
su
per induzione transfinita.
- Dimostrare che esiste un insieme
di punti del piano
tali che ogni retta nel piano contenga esattamente due punti di
.
- Dimostrare che esiste una funzione
che non sia monotona su nessun sottoinsieme di
della cardinalità del continuo.
- Dimostrare che ogni funzione da
in
si scrive come somma di due bigezioni da
in
.
Complementi di matematica – Esercitazione del 20/4
Equazioni differenziali
83. Per ogni punto del piano con
passa un’unica ellisse
(con
). Descrivere la famiglia di curve che in ogni punto sono ortogonali all’ellisse passante per quel punto.
84. Sia un intervallo aperto. Sia
una funzione continua positiva, e sia
una funzione differenziabile che risolve l’equazione differenziale
: mostrare che o
è sempre crescente, nel qual caso si ha
per ogni
, oppure è sempre decrescente, nel qual caso si ha
; dunque
è di classe
.
85. Descrivete tutte le funzioni differenziabili che risolvono
; mostrare che sono
e in effetti
a tratti.
86. Sia una funzione
tale che
e
per ogni
. Si provi che la funzione
è identicamente nulla.
87. Determinare la soluzione generale dell’equazione differenziale
88. Discutere le soluzioni di
studiandone in modo qualitativo l’esistenza (locale o globale) delle soluzioni, le proprietà di monotonia e convessità/concavità.
89. Per il problema di Cauchy
mostrate che esiste unica la soluzione globale , e che
è limitata e esistono finiti i limiti
e
.
90.Discutete l’equazione differenziale
per , studiando in modo qualitativo l’esistenza (locale o globale) delle soluzioni, le proprietà di monotonia e convessità/concavità. Mostrate che la soluzione esiste per tutti i tempi positivi, ma che per
non si estende a tutti i tempi negativi. Mostrate che esiste un
critico tale che, per
la soluzione non si estende a tutti i tempi negativi, mentre per
la soluzione esiste per tutti i tempi negativi; inoltre per
si ha
.
91. Consideriamo l’equazione differenziale , dove
è una funzione continua. Dimostare che tutte le soluzioni con
esplodono in tempo finito se e solo se
. L'ipotesi che
è davvero necessaria?
92. Si consideri il problema di Cauchy ,
, dove
è una funzione continua. Dimostrare che c'è esistenza globale (nel futuro) se e solo se
,
93. Consideriamo l’equazione differenziale . Dimostrare che, se
è una funzione continua e limitata, allora l’equazione ammette esattamente una soluzione limitata su tutta la retta.
Consideriamo l’equazione differenziale . Dimostrare che esiste una funzione
continua e limitata e tale che l’equazione non ammette nessuna soluzione limitata su tutta la retta.
94. Consideriamo l’equazione differenziale
,
dove è un parametro reale ed
è una funzione continua.
- Dimostrare che, se
e
è limitata allora l’equazione ammette sempre esattamente una soluzione limitata su tutta la retta.
- Dimostrare che, se
, allora le soluzioni sono tutte limitate o tutte illimitate, ed entrambi i casi si possono realizzare per opportune scelte di
.
- Dimostrare che, qualunque sia il valore di
, se
è periodica allora l’equazione ammette esattamente una soluzione periodica.
95. Determinare la soluzione generale dell’equazione differenziale
Complementi di Matematica – Esercitazione del 28/3
Curve
71. Disegnare una rappresentazione approssimativa delle seguenti curve in e calcolarne la lunghezza in funzione del parametro
:
- (Astroide)
, per
;
- (Cardioide) l'insieme dei punti della forma
, dove
.
72. Dimostrare che la lunghezza dell'ellisse (con
,
) è
, con
.
73. Dati reali positivi, definiamo le due successioni
ponendo
,
,
. Mostrare che le due successioni tendono allo stesso limite finito e positivo, che chiameremo
.
74. Dimostrare che, dati reali positivi e detto
, vale
, con la notazione dell'esercizio precedente. Hint: con un cambio di coordinate, dimostrare che
.
75. Disegnare la Lemniscata di Bernoulli, cioè l'insieme dei punti del piano tali che
. Mostrare che si tratta di una curva la cui lunghezza totale è
.
Teorema della funzione implicita
☞ 76. Sia data da
. Sia
. Mostrare che
è in
e che esistono funzioni reali
tali che
in un intorno di
. Scrivere equazioni per la retta tangente a
in
.
77. Dato un sottoinsieme di
, dimostrare che le seguenti condizioni sono equivalenti:
- è localmente diffeomorfo a un aperto di ;
- è localmente il grafico di una funzione liscia che esprime delle coordinate in funzione delle altre
;
- è localmente la controimmagine di per una funzione da
a
il cui differenziale in
abbia rango
;
- è localmente l'immagine di una funzione liscia da in
il cui differenziale abbia rango massimo.
78. Sia una funzione
da
nelle matrici simmetriche
, considerate nello spazio euclideo
. Supponiamo che
sia un autovalore di
di molteplicità 1. Dimostrare che esistono
e una funzione
con
tali che
sia un autovalore di
di molteplicità 1 per
. Dimostrare che
, dove
è un autovettore di
relativo a
di norma Euclidea uguale a
.
79. Sia una funzione
da
in sé. Mostrare che localmente una fra
e
è funzione dell'altra (si può scrivere
o
in un appropriato intorno di
).
80. Sia un aperto di
contenente il punto
e sia
una funzione tale che
,
,
. Sia inoltre
. Dimostrare che, per un opportuno intorno
di
,
è l'unione di due grafici di funzioni
che si intersecano trasversalmente (i.e. che hanno tangenti non coincidenti in
). Di conseguenza,
non è localmente il grafico di una funzione in una variabile intorno a
.
Moltiplicatori di Lagrange
81. Siano funzioni reali
su un aperto
di
. Dato
, sia
e si supponga
per
. Mostrare che, se
è tale che
, allora esiste
tale che
.
82. Siano come nell'esercizio precedente, e assumiamo che
siano
. Sia
; mostrare che se
allora
, dove
è l'Hessiana di
in
.
Ecco una traccia (in verità abbastanza dettagliata) di soluzione per gli ultimi due problemi, che non avevamo corretto per bene a esercitazione; notare che questa soluzione non è la più rapida che si possa produrre, ma è completamente elementare! Moltiplicatori di Lagrange
Complementi di Matematica – Esercitazione 2/3/2022
Perdonate la lista degli esercizi arrivata tardissimo: avete però un sacco di tempo per pensarci, perché come dicevamo l'altra volta correggeremo esercizi vecchi questo giovedì (chi non ha risposto al questionario potrebbe a questo punto farlo, se possibile entro domani, anche solo segnalando i problemi che vuole vedere corretti se ne ha!). Notate che nella seconda parte di questa mandata ci sono (anche) esercizi sugli argomenti che tratterete oggi a lezione. Vi pubblicherò con calma un'ulteriore mandata di esercizi di calcolo differenziale quando l'avrete fatto, e poi ne correggeremo un po' insieme dopo i colloqui.
Convergenza uniforme
☞ 56. Per le seguenti successioni di funzioni da in
, si determini l'insieme dei punti sui quali convergono e se su tale insieme convergono o meno uniformemente:
;
;
;
.
☞ (importante ma non banale) 57. [Svolto il 28/3] Sia una successione di funzioni reali continue su un compatto
di
, decrescente nel senso che per ogni
si abbia
su
, che converga puntualmente a una funzione continua
su
. Dimostrare che la convergenza è in realtà uniforme. Questo risultato sarebbe vero se non fossimo su un compatto? Se il limite non fosse continuo? Se non si avesse definitivamente
?
☞ 58. [Svolto il 28/3] Sia una successione di funzioni reali continue definite su un intervallo chiuso
, ciascuna debolmente crescente, che convergano puntualmente verso una funzione
continua su
. Si dimostri che la convergenza è uniforme.
59. Dimostrare che l'indicatrice dei razionali non è limite puntuale di funzioni continue.
Serie di funzioni
☞ (almeno alcune!) 60. Discutere la convergenza (puntuale/assoluta/uniforme/totale) delle seguenti serie di funzioni
61. [Svolto il 28/3] Sia la somma della serie di potenze
su
. Supponiamo che la serie converga in un punto
, con somma
. Si provi che allora la serie converge uniformemente nel segmento di estremi
e
, e che
.
Una volta dimostrato questo, confronta con il più forte Teorema 6.33 delle note del corso!
62. Siano successioni di funzioni da uno spazio metrico in
tali che
- la serie delle
ha somme parziali uniformemente limitate in
;
uniformemente su
;
per ogni
.
Si dimostri che la serie converge uniformemente su
.
63. Sia una radice primitiva
-esima dell'unità per
; dimostrare che
converge uniformemente sui compatti di
.
☞ 64. Si calcoli lo sviluppo in serie delle funzioni ,
,
,
,
,
,
,
intorno a 0, se ne determini il raggio di convergenza e l'insieme di convergenza.
65. [Svolto il 28/3] Si dimostri che e che
.
☞ 66. Data una matrice su
definiamo il suo esponenziale
come
\(\sum_{k=0}^{\infty} A^k/k\)
. Dimostrare che tale serie converge per ogni (nel senso della distanza indotta da una qualunque norma su
). Mostrare inoltre che
.
67. Si provi che, se e
(matrici
su
come sopra) commutano allora
. È vero se
e
non commutano? Cosa si può dire sull'invertibilità della matrice
?
68. Si dimostri che se è tale che tutte le sue derivate siano non negative allora è analitica.
☞ 69. Si dimostri che è analitica su tutto
ma che il suo raggio di convergenza del suo sviluppo centrato in
è
.
☞ 70. Calcolare il raggio di convergenza delle seguenti serie di potenze:
Complementi di Matematica – Esercitazione 23/2/2023
Come promesso, un set di esercizi un po' più tardivo e un po' più scarno per questa volta!
Sia una funzione. Un modulo di continuità per
è una funzione
debolmente crescente e continua in
tale che si abbia
,
per
.
47. Dimostrare che ha un modulo di continuità se e solo se è uniformemente continua.
48. Dimostrare inoltre che, se ha un modulo di continuità, ne ha uno che sia continuo dove non è infinito.
49. Dimostrare che, se è un intervallo e
è
con la distanza euclidea,
è uniformemente continua se e solo se ammette modulo di continuità finito. Cosa si può dire in generale sull'esistenza o meno di un modulo di continuità finito?
50. Supponiamo che sia completo e consideriamo
, dove
. Mostrare che, se
è uniformemente continua, allora si estende in modo unico a una funzione
continua, che è anche uniformemente continua. Se
è compatto si può in effetti caratterizzare così la continuità uniforme:
è uniformemente continua se e solo se si estende a
continua.
51. Mostrare (idealmente utilizzando il modulo di continuità!) che se è uniformemente continua, allora esistono costanti positive
tali che
per
.
52. Dimostrare che se (con
intervallo) è
-Hölderiana con
allora è costante.
53. Costruire (se esiste) un esempio di funzione in ciascuna categoria: uniformemente continua ma non Hölderiana;
continua ma non uniformemente continua;
uniformemente continua fra spazi metrici che non sia limitata su ogni limitato;
continua e non monotona su nessun intervallo.
54. Dimostrare che esiste una topologia sull'insieme delle funzioni da a
tale che
secondo questa topologia se e solo se le
convergono a
puntualmente, ma che non esiste una metrica che induca questa topologia.
55. È vero che, se funzioni da
in
convergono uniformemente e le
sono uniformemente continue, allora il limite
è uniformemente continuo? È vero se, anziché la convergenza uniforme su
, vale la convergenza uniforme su tutti i compatti
?
Complementi di Matematica – Esercitazione 16/2/2023
Spazi metrici e topologie indotte
☞ 31. Dato uno spazio metrico , sia
una funzione debolmente crescente e subadditiva, cioè tale che si abbia
per
, tale che
. Mostrare che
è ancora una distanza su
. Mostrare che se
è continua in 0 allora la topologia generata da
è la stessa della topologia generata da
. Il viceversa è vero?
☞ 32. Sia una successione di elementi di uno spazio vettoriale
dotato di una distanza ultrametrica (vedi definizione nelle note)
che sia invariante per traslazioni e lo renda completo; si dimostri che la serie (i.e. la successione delle somme parziali) degli
converge in
se e solo se
in
.
33. Sia uno spazio vettoriale su
. Una norma su
è una funzione
tale che valgano:
se e solo se
;
per ogni
;
per ogni
.
Dimostrare che, se è una norma, allora
è una distanza su
. Dimostrare che, date due norme su uno spazio
di dimensione finita, le loro distanze corrispondenti sono bi-Lipschitz equivalenti. La conclusione vale anche per
di dimensione infinita?
☞ 34. Mostrare che (con la metrica euclidea) e
(con la metrica prodotto fra la metrica geodetica e quella euclidea) sono omeomorfi (per le rispettive topologie indotte) ma non isometrici.
35. Fornire, se esiste, un esempio di uno spazio topologico compatto ma non sequenzialmente compatto e un esempio di spazio topologico sequenzialmente compatto ma non compatto.
36. Sia uno spazio metrico tale che ogni funzione continua da
in
abbia massimo. Dimostrare che
è compatto.
Razionali e interi -adici
☞ 37. Su , si consideri la distanza
-adica descritta dalle note del corso. Si dimostri che è una ultrametrica (vedi note) e che
non è completo per questa distanza. Sia
un completamento del suddetto spazio metrico; dimostrare che le palle chiuse in
(i.e. gli insiemi della forma
, con
intero positivo) sono sia chiuse che aperte. Dimostrare che
(con la topologia indotta dalla distanza
-adica) è totalmente disconnesso e T2.
38. Si dimostri che lo spazio metrico degli interi
-adici, dato dalla palla
nella notazione dell'esercizio precedente, è compatto e omeomorfo a
per qualunque intero
e
.
La distanza di Hausdorff
☞ 39. Sia uno spazio metrico e siano
due chiusi disgiunti. Dimostrare che esiste una funzione continua
tale che
e
. Dedurre che esistono due aperti disgiunti
tali che
,
.
40. La tesi dell'esercizio 39 è vera per ogni spazio topologico T2?
41. Sia uno spazio metrico. Sia
l'insieme dei chiusi limitati di
(cioè dei chiusi
tali che
). Dato
e
, scriviamo
per
. Si consideri la funzione
che manda
in
. Dimostrare che
è una distanza su
.
42. Dimostrare che, se è compatto, allora
è compatto. Se lo spazio
è completo, è vero che
è completo?
43. Mostrare che le approssimazioni standard della stella di Koch convergono formalmente verso la stella di Koch secondo la distanza , e similmente per i soliti chiusi la cui intersezione dà il Cantor.
Metrizzabilità e isometrie
44. Uno spazio topologico è metrizzabile se esiste una metrica sullo spazio che induca la sua topologia. Determinare, per i seguenti spazi, se sono o meno metrizzabili (se sì, esibire una metrica appropriata): qualunque spazio con la topologia discreta; la retta di Sorgenfrey; la topologia di Zariski su infinito; la topologia d'ordine su
data dall'ordine "
se e solo se
o
e
"; la topologia d'ordine data dall'ordine sopra descritto su
.
45. Dato uno spazio metrico , sia
lo spazio metrico delle funzioni da
a
con la distanza del sup (
). Dimostrare che, qualunque sia
,
è completo.
46. Dimostrare che qualunque spazio metrico è isometrico a un sottoinsieme di
(consiglio: provate a dimostrarlo prima nel caso in cui
sia limitato). Dedurre che ogni spazio metrico la cui cardinalità non sia più che quella di
si può immergere isometricamente in
.
Complementi di Matematica – Esercitazione 9/2/2023
Breve nota: anziché segnare alcuni esercizi come "più difficili" o extra, ho deciso di indicare con ☞ un sottoinsieme degli esercizi "minimale" che consiglio a tutti di assicurarsi di essere capaci di svolgere e – cosa non scontata – scrivere bene. Nessuno dei problemi ☞ dovrebbe porre difficoltà insormontabili (a meno di typo o errori in qualche esercizio, che sono ovviamente possibili e che vi prego di far presenti a esercitazione!). Buon weekend e buon lavoro!
Alcuni esempi di spazi topologici
☞ 16. [Svolto 16/2] (Retta di Sorgenfrey) Su , si consideri la topologia generata dagli intervalli della forma
con
. Mostrare che è una topologia strettamente più fine di quella standard (gli aperti "normali" sono tutti aperti in questa topologia, ma non viceversa). Quali sottoinsiemi in questa topologia sono connessi? Cosa riuscite a dire sui sottoinsiemi compatti in questa topologia?
☞ 17. [Svolto 16/2] (Topologia d'ordine) Dato un insieme dotato di un ordine totale
, la topologia d'ordine su
è quella generata dagli insiemi della forma
e
, dove
. Ad esempio, la topologia di
è la sua topologia d'ordine per l'ordinamento standard. Mostrare un esempio di sottoinsieme di
la cui topologia indotta non sia quella d'ordine.
18. [Svolto 16/2] (Topologia di Zariski) Sia un campo. Dato un insieme
di polinomi in
, chiamiamo
l'insieme degli zeri comuni a tutti gli elementi di
(
). Dimostrare che la collezione di sottoinsiemi di
che sono della forma
per un qualche
è l'insieme dei chiusi di una topologia su
, detta topologia di Zariski. Mostrare che lo spazio
dotato di tale topologia non è T2 (cioè Hausdorff) a meno che
non sia finito (nel qual caso, in cosa consiste la topologia di Zariski?) Dimostrare che, se
è infinito, interpretando
come l'insieme delle matrici
a coefficienti in
, le matrici invertibili sono dense in
per la topologia di Zariski. Utilizzare questo fatto per dimostrare il Teorema di Binet.
☞ 19. [Svolto 16/2] Per tutte le possibili coppie di spazi della lista seguente, esibire un omeomorfismo fra i due o dimostrare che i due spazi non sono omeomorfi: .
20. Dimostrare che ed
non sono omeomorfi (pensateci, ma questo è più difficile di quanto non sembri e certamente facoltativo)!
Compattezza, connessione
☞ 21. [Svolto 16/2] Dimostrare che un compatto in uno spazio T2 è chiuso e fornire un esempio di un compatto non chiuso. Dimostrare che una funzione continua e bigettiva da uno spazio compatto a uno spazio T2 è un omeomorfismo. L'affermazione rimane vera rilassando l'ipotesi "compatto" o l'ipotesi "T2"?
☞ 22. [Svolto 16/2] Dimostrare che, data una successione di compatti chiusi non vuoti "annidati" in uno spazio topologico
tale che per
, l'intersezione
è non vuota. Si può eliminare la condizione "compatti"? Si può eliminare la condizione "chiusi"? (Questo è un lemma IMPORTANTE che forse avrete visto o vedrete a lezione: siate capaci di dimostrarlo e tenetelo presente come strumento da usare!)
☞ 23. [Svolto 16/2] Esiste una funzione continua bigettiva da in
?
☞ 24. L'insieme , dove
è una retta, è connesso? L'insieme
, dove
è un sottospazio affine di dimensione (su
) 1, è connesso?
25. Dimostrare che la chiusura dell'insieme è connessa, ma non connessa per archi.
Topologia prodotto
☞ 26. Dimostrare che le proiezioni per la topologia prodotto sono continue e aperte. Dimostrare che una funzione da uno spazio topologico a un prodotto di spazi topologici è continua se e solo se lo sono le sue composizioni con le proiezioni canoniche.
☞ 27. Dimostrare che prodotto di T2 è T2 e che prodotto di connessi è connesso. Dimostrare che il prodotto di due spazi compatti è compatto.
28. Dimostrare che, con la box topology generata da tutti i rettangoli (e non dai soli insiemi cilindrici) il prodotto di spazi topologici compatti non è necessariamente compatto. Dimostrare che la funzione da
in
è continua se su
si considera la topologia prodotto, ma non se su
si considera la box topology.
29. Dimostrare che lo spazio con la topologia prodotto (di una quantità numerabile di copie della topologia discreta su
) è omeomorfo all'insieme di Cantor con la topologia indotta dalla topologia di
.
30. [Parzialmente svolto 16/2] Ecco una caratterizzazione alternativa forse un po' sorprendente della compattezza. Dimostrare che uno spazio topologico è compatto se e solo se per ogni spazio topologico
la proiezione
è chiusa.
Complementi di Matematica – Esercitazione 2/2/2023
Chiusure, parti interne, frontiere, palle in
1. [Svolto 2/2] Che relazioni di contenimento esistono fra e
, fra
e
, fra
e
, fra
e
? (Quando una relazione di contenimento non è vera in generale, fornire un controesempio.)
2. [Svolto 2/2] Che relazioni di contenimento esistono fra ? (Quando una relazione di contenimento non è vera in generale, fornire un controesempio.)
3. [Svolto 2/2] Dimostrare che ogni aperto di è un'unione disgiunta numerabile di intervalli aperti (i.e. intervalli della forma
, con
e
in
).
4. [Svolto 2/2] È vero che ogni aperto di è unione numerabile di palle aperte? È vero che ogni aperto di
è unione di palle aperte disgiunte?
5. [Svolto 9/2] Quali sono i sottoinsiemi di che sono sia chiusi sia aperti? E quelli di
?
6. Si può esprimere come unione numerabile di intervalli chiusi disgiunti?
Una digressione sulla dimensione di Minkowski
Dato un insieme limitato in
e dato
, definiamo
come il minimo
tale che esistano
per cui
, i.e. il minimo numero di palle aperte di
sufficiente per coprire l'insieme
. Definiamo la dimensione di Minkowski superiore di
come
similmente si definisce la dimensione di Minkowski inferiore come il corrispondente e, se le due coincidono, il loro valore è detto semplicemente dimensione di Minkowski e denotato con
.
7. [Svolto 2/2] Mostrare che, per , con
, si ha
.
8. [Svolto 2/2] Mostrare che, per , si ha
.
9. Mostrare le seguenti proprietà (enunciate per la dimensione superiore, ma valide anche per quella inferiore):
;
- se
,
;
(cosa si può dire nel caso di un'unione numerabile?);
- Se
è finito, allora
.
10. Dato limitato ed
, definiamo le seguenti quantità:
Mostrare che la dimensione di Minkowski (superiore/inferiore) si può definire equivalentemente con qualunque di queste quantità al posto di .
11. Calcolare .
12. Calcolare , dove
è l'insieme di Cantor.
13. Produrre un esempio di insieme per il quale la dimensione di Minkowski superiore e quella inferiore non coincidono.
14. Calcolare .
15. Dimostrare che, se è una funzione reale
su
, allora il suo grafico
ha dimensione di Minkowski 1. Riuscite ad indebolire la condizione
? In particolare, lo statement è vero per una funzione continua?
Random Edge Flips and Random Planar Maps
A long-standing problem proposed by David Aldous is that of giving a sharp upper bound for the mixing time of the so-called triangulation walk, a Markov chain defined on the set of all possible triangulations of the regular n-gon. A single step of the chain consists in performing a random edge flip, i.e. in choosing an (internal) edge of the triangulation uniformly at random and, with probability 1/2, replacing it with the other diagonal of the quadrilateral formed by the two triangles adjacent to the edge in question.
Edge flips are a simple dynamic that can be considered on a range of different models, such as planar maps, p-angulations of the sphere, lattice triangulations, and other geometric graphs; iterating random edge flips will eventually yield an almost uniform random structure of a given size — but how many iterations does it take to come reasonably near to stationarity? This proves to be an elusive question even in the (deceptively) simple case of the triangulation walk, for which it remains mostly open.
We will take this problem as a starting point to discuss the mixing and relaxation time of reversible Markov chains. At the same time, we will explore the rich world of planar maps, from surprising combinatorial features to their role as universal models for random surfaces.
Finally, we will present some new results obtained in joint work with Alexandre Stauffer, briefly describing some tools we have developed in order to provide polynomial upper and lower bounds for the mixing time of edge flips on a range of Catalan structures.