COMBINATORIA
LAUREA MAGISTRALE IN MATEMATICA APPLICATA
(Nuovo programma: sito in aggiornamento) a.a. 2022/23


Programma del corso
Avvisi
Testi consigliati
Esami
Diario delle Lezioni
Esercizi proposti

 
 
Docente Num. Telefono E-mail Orario Ricevimento Stanza
Claudia Malvenuto 06 4991 3210 claudia@mat.uniroma1.it Su appuntamento per email 105

Le lezioni daranno solo in in presenza, in Aula G, Dipartimento di Matematica Guido Castelnuovo

Codice corso Classroom 2utger7
È *necessario* iscriversi al corso seguire queste semplici istruzioni, usando l'indirizzo istituzionale Sapienza:
Vai a classroom.google.com.
Nella pagina Corsi, fai clic su Aggiungi + > Iscriviti al corso.
Inserisci il codice 2utger7
poi fai clic su Iscriviti.
link di invito https://classroom.google.com/c/NTQ4ODMzMjYyNjgy?cjc=2utger7
In questo modo mi sarà possibile ottenere in automatico una mailing list. Il link degli appunti - prodotti col tablet - delle lezioni, che verranno proiettate su schermo in Aula G solo in presenza, insieme a ulteriori informazioni, vi verranno sempre comunicate attraverso lo "stream" di Classroom, se avrete completato i tre punti precedenti.

Orario lezioni: giovedì dalle 9:00 alle 11:00 e venerdì dalle 14:00 alle 16:00 in aula G, Matematica.

Inizio lezioni: mercoledì 22 settembre 2022
Fine lezioni prevista: lunedì 22 dicembre 2022. (a meno che non si rendano necessarie cancellazioni impreviste).

Durata: il corso da 6 crediti prevede 48 ore di lezione.


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.

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

Torna su


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
Primo appello:
Scritto: ... gennaio 2022 ore ... Aula ...
Orale: ... gennaio 2022 ore ... Aula ...

Secondo appello:
Scritto: ... febbraio 2022 ore ... Aula ...
Orale: ... febbraio 2022 ore ... Aula ...

SESSIONE ESTIVA
Primo appello:
Scritto: ... giugno 2022 ore ... Aula ...
Orale: ... giugno 2022 ore ... Aula ...

Secondo appello:
Scritto: ... luglio 2022 ore ... Aula ...
Orale: ... luglio 2022 ore ... Aula ...

SESSIONE AUTUNNALE
Primo appello:
Scritto: ... settembre 2022 ore Aula ...
Orale: ... settembre 2022 ore ... Aula ...

Torna su


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).
  • Torna su


    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).
  • Siti utili

  • http://mathworld.wolfram.com/topics/DiscreteMathematics.html
  • On-line encyclopedia of Integer Sequences.
  • Torna su


    Diario delle lezioni

    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.

    OTTOBRE NOVEMBRE DICEMBRE

    1) Giovedì  22 settembre:
    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) Venerdì  23 settembre:
    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) Giovedì  29 settembre:
    Definizione di passeggiata, cammino, cammino semplice, circuito, ciclo. La relazione di equivalenza della raggiungibilità. Connessione. La distanza in un grafo. Circuiti euleriani. Caratterizzazione di Eulero.
    [App] Capitolo 1.4
    [M-N] Capitolo 4.1

    4) Venerdì  30 settembre:
    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. 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.3 e 1.4
    [M-N] Capitolo 4.1

    5) Giovedì  6 ottobre:
    Algoritmo di Kruskal per la ricerca di un albero di copertura di uyn grafo connesso di costo minimo.

    [App] Capitolo 1.5

    6) Venerdì  7 ottobre:
    Teorema di Cayley. Prima dimostrazione: il codice di Prüfer.
    Esercizi della Scheda n.2

    [App] Capitolo 2.1 e 2.2

    7) Giovedì  13 ottobre:
    Seconda dimostrazione: i vertebrati di Joyal. Coefficienti binomiali, interpretazioni combinatorie.

    [App] Capitolo 2.3 3 2.4

    8) Venerdì  14 ottobre:
    I coefficienti multinomiali. Dimostrazione ricorsiva del Teorema di Cayley.
    Esercizi della Scheda n.3

    [App] Capitolo

    9) Giovedì  20 ottobre:

    [App] Capitolo

    10) Venerdì  21 ottobre:

    esercizi della Scheda n.

    [App] Capitolo

    11) Giovedì  27 ottobre:

    [App] Capitolo 12) Venerdì  28 ottobre:

    esercizi della Scheda n.

    [App] Capitolo

    13) Giovedì  3 novembre:

    [App] Capitolo

    14) Venerdì  4 novembre:

    esercizi della Scheda n.

    [App] Capitolo

    15) Giovedì  10 novembre:

    [App] Capitolo

    16) Venerdì  11 novembre:

    esercizi della Scheda n.

    [App] Capitolo

    17) Giovedì  17 novembre:

    [App] Capitolo

    18) Venerdì  18 novembre:

    esercizi della Scheda n.

    [App] Capitolo

    19) Giovedì  24 novembre:

    [App] Capitolo

    20) Venerdì  25 novembre:

    esercizi della Scheda n.

    [App] Capitolo

    21) Giovedì  1 dicembre:

    [App] Capitolo

    22) Venerdì  2 dicembre:

    esercizi della Scheda n.

    [App] Capitolo

    *) Giovedì  8 dicembre:
    Festività

    [App] Capitolo

    24) Venerdì  9 dicembre:

    esercizi della Scheda n.

    [App] Capitolo


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