Combinatorics 2025/26   

Combinatorics

LAUREA MAGISTRALE IN MATEMATICA APPLICATA

• a.a. 2025/26 

• a.a. 2024/25 

• a.a. 2023/24 

Professor: Claudia Malvenuto

Phone number: 06 4991 3210

E-mail: claudia@mat.uniroma1.it

Office hours: By appointment via email

Room: 105

Classroom code 6evftkwf
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 6evftkwf
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 3pm to 5pm in Classroom G, Matematica. 

Lecures are in-person, Classroom G, Dipartimento di Matematica Guido Castelnuovo

First course: Monday 29 September 2025

The last class will probably be on Tuesday 13 January 2026

Duration: The 6-credit course includes 48 hours of lecture time.

Notices

* 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.

* Blog of Peter Camerong

* 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).

Exams

* 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.

ATTENZIONE! La prova scritta sarà in un'unica data alla fine del corso!

* Gli appelli non sono ancora aperti su InfoStud.

SESSIONE INVERNALE
Primo appello:
19 gennaio 2026 ore ... Aula ...

Secondo appello:
4 febbraio 2026 ore ... Aula ...

SESSIONE ESTIVA
Primo appello:
15  giugno 2026 ore ... Aula ...

Secondo appello:
3 luglio 2026 ore ... Aula ...

SESSIONE AUTUNNALE
Primo appello:
2 settembre 2026 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.
* Il programma completo e dettagliato del corso si ottiene solo consultando il diario delle lezioni.

Programma di massima (provvisorio)

• Combinatoria estremale (Teorema di Sperner, massima cardinalità di una famiglia intersecante, Teorema di Erdos-Ko-Rado, Teoria di Ramsey e numeri di Ramsey. Generalizzazione del principio dei cassetti).

Testi Consigliati

Dispense del corso di Combinatoria di János Körner e Claudia Malvenuto.

Dispense del corso di Combinatoria di Antonio Machì.

Béla Bollobaś, Modern Graph Theory, Graduate Texts in Mathematics, n 184, Springer.

Reinhard Diestel, Graph Theory, Graduate Texts in Mathematics, n 173, Springer.

J.H.van Lint, R.M.Wilson, A course in Combinatorics, 2nd edition. Cambridge University Press (1992).
Altri testi consultabili

Martin Aigner, Günter Ziegler, Proofs from THE BOOK, Springer.

J.Matousek, J.Nesetril, Invitation to Discrete Mathematics. Clarendon Press (1998).

R.L.Graham, D.E.Knuth, O.Patashnik, Matematica Discreta. Hoepli (1992).

Sitography

http://mathworld.wolfram.com/topics/DiscreteMathematics.html

On-line encyclopedia of Integer Sequences.

Assignments

• Scheda n.1 pdf (gradi, isomorfismo, circuiti, connessione)

• Scheda n.2 pdf (distanza, connessione, alberi)

• Scheda n.3 pdf (binomiale)

• Scheda n.4 pdf (coefficienti multinomiali, enumerazione)

• Scheda n.5 pdf (permutazioni)

• Scheda n.6 pdf (enumerazione di sottografi, stringhe)

• Scheda n.7 pdf (colorazioni)

• Scheda n.8 pdf (combinatoria estremale, il principio dei cassetti)

• Scheda n.9 pdf (teoria estremale degli insiemi)

• Scheda n.10 pdf (principio di inclusione ed esclusione)

• Scheda n.11 pdf (numeri di Catalan, posets, enumerazione)

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.

1) Monday 29 September (1-2):
Introduzione al corso: modalità  degli esami, ricevimento, libri di testo etc. Prime definizioni: grafo, grafo semplice, orientato, con cappi, con archi multipli. Grafo completo.
[App] Capitolo 1.1
[M-N] Capitolo 3.1

2) Tuesday 30 September (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 6 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 coprodotto di grafi, di posets, di parole). Circuiti euleriano, definizione.
[App] Capitolo 1.4
[M-N] Capitolo 4.1

4) Tuesday 7 October (7-8):
Caratterizzazione dei circuiti euleriani: un grafo senza punti fissi è un circuito euleriano se e solo se ogni vertice ha grado pari. 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) Thursday 9 October Aula F (9-10):
Definizione di famiglie di insiemi massimali o minimali (massimalità e minimalità rispetto a una proprietà). Clique e stabili. Stability numner and clique number. Caratterizzazione degli alberi: un grafo è un albero se e solo se è aciclico massimale se e solo se è connesso minimale. Proposizione: in un albero c'è almeno un vertice di grado 1. Proposizione: ogni grafo connesso ammette un sottografo ricoprente che sia un albero. Teorema di Bondy. Quanti sono  gli alberi di copertura di un fissato grafo G?  Esercizi della Scheda n.2
[App] Capitolo 2.1 e 2.2
[App] Capitolo 1.5

6) Monday 13 October (11-12):
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

7) Tuesday 14 October (13-14):
Teorema di Cayley. Prima dimostrazione: il codice di Prüfer. Seconda dimostrazione: i vertebrati di Joyal.
Esercizi della Scheda n.3
[App] Capitolo

8) Thursday 16 October Aula F (15-16):
Fine della dimostrazione del teorema di Joyal. Coefficienti binomiali, interpretazioni combinatorie.
[App] Capitolo

9) Monday 20 October (17-18):
Multinomial coefficients, combinatorial interpretations.  Recursive proof of Cayley's Theorem via multinomials. Dyck paths, definition, enumeration. The Catalan numbers. Recursion. Non crossing partitions.
esercizi della Scheda n. 3. e 4.
[App] Capitolo

10) Tuesday 21 October (19-20):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

Updated up to here

11) Monday 27 October (21-22):
End of proof of the Theorem of Brooks. Bipartite graphs.
esercizi della Scheda n.
[App] Capitolo

12) Tuesday 28 October (23-24):  Esercitazione in classe
esercizi delle prime 7 schede
13) Monday 3 November (25-26):
Hypercube. Hamming distance. Characterization of bipartite graphs. A tree is bipartite. A Theorem of Erdos. [App] Capitolo

14) Tuesday 4 November (27-28):
Extremal combinatorics. Maximum number of edges for a non connected graph. Mantel-Turàn Theorem.
[App] Capitolo

15) Monday 10 November (29-30):
Extremal set theory. Type of problems. The Sperner Theorem. Antichains in posets. Intersecting families
esercizi della Scheda n.
[App] Capitolo

16) Tuesday 11 November (31-32):
Erdos-Ko-Rado theorem.
[App] Capitolo

17) Monday 1 December (33-34):
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.
[App] Capitolo

18) Tuesday 2 December (35-36):
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

19) Tuesday 9 December (37-38):
Hall Theorem for 0-1 matrices. The Hall theorem for bipartite graphs
[Appunti di Machì] Capitolo

20) Monday 15 December (39-40):
Koenig-Egervary Theorem.
[Appunti di Machì] Capitolo

21) Tuesday 16 December (41-42):
Teorema di Birkoff von Neumann. Il principio dei cassetti. Teoria di Ramsey
[Appunti di Machì] Capitolo

22) Thursday 18 December  Aula IV ore 14-16 (43-44):
Prova scritta finale obbligatoria per tutti.
[App] Capitolo

23) Monday 22 January (45-46):
Teorema di Birkoff von Neumann. Il principio dei cassetti. Teoria di Ramsey
[Appunti di Machì] Capitolo

24) Monday 12 January (47-48):
Tesine

24) Tuesday 13 January (47-48):
Tesine

Sito in costruzione, ultimo aggiornamento: 3 ottobre 2025.
Per commenti/correzioni al sito scrivere a C. Malvenuto, indicando nel subject un riferimento al sito del corso di Combinatoria.