|
|
|
|
|
|
|
|
|
| Professor | Phone number | Office hours | Room | |
| Claudia Malvenuto | 06 4991 3210 | claudia@mat.uniroma1.it | By appointment via email | 105 |
Lecures will be in-person, Classroom G,
Dipartimento di Matematica
Guido Castelnuovo
Classroom code 2utger7
To register to the course in Combinatorics please follow these instructions,
using your official Sapienza email address:
Go to classroom.google.com.
In the page Corsi, clic on Aggiungi + > Iscriviti al corso.
Insert the code 2utger7
then clic on Iscriviti.
Invitation link https://classroom.google.com/c/NTQ4ODMzMjYyNjgy?cjc=2utger7
Any information about the course will be communicated via the
"stream" of Classroom.
Schedule of the classes: Monday 10am to 12am and Tuesday 2pm to 4pm in Classroom G, Matematica.
First course:
Monday 22 September 2024
The last class will probably be on Tuesday 17 December 2024
Avvisi
* Un articolo importante, tratto dal settimanale Internazionale,
La fiducia delle donne:
studiano, lavorano e fanno carriera, ma arrivano raramente ai vertici.
Perché le donne restano indietro?
Leggete la risposta provocatoria di due giornaliste al problema.
* Qui trovate la
Dispensa III sulla teoria di Ramsey dagli appunti di
Antonio Machì.
* Una bella
pagina web sulla Teoria di Ramsey di Neil Lyall, con alcuni appunti di
teoria di Ramsey aritmetica.
* Estremal combinatorics of permutations according to
Gil Kalai and to Peter
Cameron
* Pagina di Robin Thomas sul
Teorema dei quattro colori
e un articolo dei Notices of the AMS:
Un Update on the Four-Color Theorem.
* Un esempio di combinatoria enumerativa da non seguire!
(Da "Monty Python and the Holy Grail")
*
Endre Szemerédi receives the 2012 Abel Prize
"for his fundamental contributions to discrete
mathematics and theoretical
computer science and in recognition of the profound and lasting impact
of these contributions on additive number theory and ergodic theory,"
to quote the Abel Committee.
*
Terence Tao:
blog category MathCO.
* Gil Kalai:
Combinatorics and more.
* Una
opinione di Doron Zeilberger sulla matematica pura,
dai Notices AMS.
* La prefazione
del libro Concrete Mathematics
Ronald L. Graham (AT&T Bell Laboratories),
Donald E. Knuth (Stanford University)
e Oren Patashnik (Center for Communications Research).
Esami
* L'esame consiste di una prova scritta finale, della presentazione di un
argomento (con pps o alla lavagna, in inglese o in italiano) su un argomento
nuovo, e di un esame orale tradizionale.
* Gli appelli non sono ancora aperti su InfoStud.
SESSIONE INVERNALE
Secondo appello:
SESSIONE ESTIVA
Secondo appello:
SESSIONE AUTUNNALE
Primo appello:
23 gennaio 2025 ore ... Aula ...
19 febbraio 2025 ore ... Aula ...
Primo appello:
20 giugno 2025 ore ... Aula ...
17 luglio 2025 ore ... Aula ...
Primo appello:
10 settembre 2025 ore Aula ...
Programma di esame
* Fanno parte del programma di esame anche gli esercizi delle schede.
Al momento sono presenti le schede di esercizi del corso dell'anno passato,
che aveva un programma diverso.
Programma di massima (provvisorio)
* Il programma completo e dettagliato del corso
si ottiene solo consultando il
diario delle lezioni.
Testi Consigliati
Altri testi consultabili
Siti utili
Class Diary
Alla fine di ogni lezione vengono indicati i riferimenti agli
Appunti di Körner-Malvenuto
([App]), oppure al libro
"Modern Graph Theory" di Béla Bollobaś
([Boll]),
al libro
"Proofs from THE BOOK" di Aigner-Ziegler
([AZ]), o ad altri Appunti
[Appunti di Machì]
i cui riferimenti precisi trovate nella sezione dei
testi consigliati.
[App]
Capitolo 1.1
[M-N] Capitolo 3.1
2) Tuesday 1 October (3-4):
Sottografo, grado di un vertice,
grado del grafo.
Isomorfismo tra grafi. Esempi: grafi completi, cicli,
cammini, bipartiti completi.
Relazione tra gradi dei vertici e numero di archi ("Hand-shaking Lemma").
Cominciare a svolgere gli esercizi della
Scheda n. 1
[App]
Capitolo 1.2
[M-N]
Capitolo 3.2
3) Monday 7 October (5-6):
Definizione di passeggiata, cammino, cammino semplice,
circuito, ciclo.
La relazione di equivalenza della raggiungibilità.
Connessione. La distanza in un grafo.
Digressione su algebre e coalgebre in combinatoria (prodotto e coproditto di grafi, di posets, di
parole).
[App]
Capitolo 1.4
[M-N]
Capitolo 4.1
4) Tuesday 8 October (7-8):
Grafi aciclici. Definizione di albero (grafo aciclico e connesso).
Caratterizzazione degli alberi: Un grafo G è un albero
se e solo se tra due qualunque vertici c'è un unico cammino
se e solo se il grafo è connesso e |E(G)|=|V(G)|-1.
[App]
Capitolo 1.3 e 1.4
[M-N]
Capitolo 4.1
5) Monday 14 October (9-10):
Definizione di famiglie di insiemi massimali o minimali
(massimalità e minimalità rispetto a una proprietà).
Caratterizzazione degli alberi: un grafo è un albero
se e solo se è aciclico massimale se e solo se è connesso minimale.
Cominciare a svolgere gli esercizi della
Scheda n. 2
[App]
Capitolo 1.5
6) Tuesday 15 October (11-12):
Proposizione: in un albero c'è aleno un vertice di grado 1.
Proposizione: ogni grafo connesso ammette un sottografo ricoprendte che sia un albero.
Esercizi della
Scheda n.2
[App]
Capitolo 2.1 e 2.2
7) Monday 21 October (13-14):
Algoritmi greedy.
Algoritmo di Kruskal per la ricerca di un albero di copertura di uyn grafo connesso di costo minimo.
Teorema (Kruskal 1956) L'algoritmo di Kruskal produce un albero ricoprente di costo minimo.
Strutture etichettate e non etichettate.
Quanti alberi ricoprenti ammette un ciclo su n vertici? Numero di alberi di copertura di un
completo su n vertici. Enunciato Teorema di Cayley
[App]
Capitolo 2.3 3 2.4
8) Tuesday 22 October (15-16):
Teorema di Cayley. Prima dimostrazione: il codice di Prüfer. Seconda dimostrazione:
i vertebrati di Joyal.
Esercizi della
Scheda n.3
[App]
Capitolo
9) Monday 28 October (17-18):
Fine della dimostrazione del teorema di Joyal.
Coefficienti binomiali, interpretazioni combinatorie.
[App]
Capitolo
10)Tuesday 29 October (19-20):
I coefficienti multinomiali. Dimostrazione ricorsiva del Teorema di Cayley.
Introduzione al numero cromatico.
esercizi della
Scheda n. 3. 3 4.
[App]
Capitolo
11) Monday 4 November (21-22):
Colorings. Chromatic number. Different upper and lower bound.
The chromatic number of a graph is at most its degree plus 1.
The Theorem of Brooks.
[App]
Capitolo
12) Tuesday 5 November (23-24):
End of proof of the Theorem of Brooks.
Bipartite graphs.
esercizi della
Scheda n.
[App]
Capitolo
13) Monday 11 November (25-26):
Hypercube. Hamming distance. Characterization of bipartite graphs.
A tree is bipartite. A Theorem of Erdos.
[App]
Capitolo
14) Monday 18 November (27-28):
Esercitazione in classe
esercizi della
Scheda n.
[App]
Capitolo
15) Tuesday 19 November (29-30):
Extremal combinatorics. Maximum number of edges for a non connected graph.
Mantel-Turàn Theorem.
[App]
Capitolo
16) Monday 25 November (31-32):
Estremal set theory. Type of problems.
The Sperner Theorem. Antichain in posets.
Intersecting families
esercizi della
Scheda n.
[App]
Capitolo
17) Tuesday 26 November (33-34):
Erdos-Ko-Rado theorem.
[App]
Capitolo
18) Monday 2 December (35-36):
Colliding permutations: some overview to a problem in extremal combinatorics of permutations.
Information Theory. The Shannon capacity of a graph. Noisy channel. The model of the graph of indistinguishability.
Graph product. Some lower bound.
esercizi della
Scheda n.
[App]
Capitolo
19) Tuesday 3 December (37-38):
The capacity of the cycles. Chvatal Theorem (no proof). Case even, case odd.
System of distinct representatives.
Hall condition for a transversal of a family of subsets.
[Appunti di Machì]
Capitolo 2
20) Monday 9 December (39-40):
Hall Theorem for 0-1 matrices. The Hall theorem
[Appunti di Machì]
Capitolo
21) Tuesday 10 December (41-42):
[Appunti di Machì]
Capitolo
22) Monday 16 December (43-44):
esercizi della
Scheda n.
[Appunti di Machì]
Capitolo
23)Tuesday 17 December (45-46):
Prova scritta finale obbligatoria per tutti
[App]
Capitolo
Sito in costruzione, ultimo aggiornamento:
22 ottobre 2024.
Per commenti/correzioni al sito scrivere a
C.Malvenuto,
indicando nel subject un riferimento al sito del corso di
Combinatoria.