COMBINATORICS

Obiettivi formativi

Obiettivi generali: acquisire le conoscenze e tecniche di base della Teoria dei grafi, alberi, circuiti, distanza, principali invarianti, algoritmi (di Kruskal e Prufer), della teoria degli ipergrafi (combinatoria estremale) e della Teoria di Ramsey, della teoria dei codici algebrici Obiettivi specifici: Conoscenza e comprensione: al termine del corso lo studente avrà acquisito le nozioni ed i risultati di base relativi alla Teoria dei grafi e ipergrafi, algebrica ed estremale e della teoria dei codici algebrici. Conoscerà anche almeno l'insieme dei problemi più significativi nell'ambito dei quali tali teorie trovano applicazioni. Applicare conoscenza e comprensione: lo studente sarà in grado di risolvere problemi di tipo algebrico-combinatorio che richiedano l'uso di tecniche legate alla combinatoria dei grafi e alle principali strutture e sottostrutture e di discutere come si possano modellizzare problemi (in ambienti non prettamente matematici) per mezzo degli strumenti acquisiti. Capacità critiche e di giudizio: lo studente avrà le basi per analizzare come argomenti della Teoria dei grafi e della teoria dei codici algebrici trattati nei corsi di base possano trovare applicazioni in diversi ambiti ed essere strumento essenziale nella soluzione di problemi concreti. Capacità comunicative: il discente avrà la capacità di comunicare in maniera rigorosa le idee ed i contenuti esposti nel corso. Capacità di apprendimento: le conoscenze acquisite permetteranno di portare avanti uno studio autonomo in un possibile contesto interdisciplinare (per coloro che hanno conoscenze ed interessi verso la Matematica Applicata, l'Informatica, la Genetica, la cosiddetta "Data Science").

Canale 1
CLAUDIA MALVENUTO Scheda docente

Programmi - Frequenza - Esami

Programma
Teoria dei grafi: concetti fondamentali. Concetti fondamentali di grafi. Connessione, distanza. Esistenza di circuiti euleriani. Gradi e numero di archi: il metodo del doppio conteggio. Teorema di Bondy. Alberi, foreste, permutazioni. Teorema di Cayley sul numero di alberi di copertura. Il codice di Prüfer. L'algoritmo di Kruskal per l'albero di copertura di costo minimo. Vertebrati e dimostrazione della formula di Cayley tramite la rappresentazione grafica di endofunzioni f:[n]->[n]. Colorazioni e Teoria di Ramsey. Grafi bipartiti. Numero cromatico. Limitazioni per il numero cromatico e il numero di stabilità in termini del grado massimo. Teoria di Ramsey per grafi. Il Teorema di esistenza di Erdös di grafi con "piccoli" numeri omega e alfa ma di "grande" numero cromatico. Combinatoria estremale. Teorema di Mantel-Turán. 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. Teoria dei codici algebrici
Prerequisiti
Algebra Lineare e Algebra 1
Testi di riferimento
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. J.H.van Lint, R.M.Wilson, A course in Combinatorics, 2nd edition. Cambridge University Press (1992).
Frequenza
In presenza
Modalità di esame
Esame scritto e orale, più una presentazione (in italiano o in inglese) su un nuovo argomento scelto da una lista di articoli proposti dal docente. Il voto finale sarà una media ponderata del voto dell'esame scritto, dell'esame orale e della presentazione.
Modalità di erogazione
Lezioni frontali, gli esercizi proposti nelle schede saranno svolti dagli studenti a casa.
  • Codice insegnamento10605748
  • Anno accademico2025/2026
  • CorsoMatematica applicata
  • CurriculumMatematica per Data Science
  • Anno2º anno
  • Semestre1º semestre
  • SSDMAT/02
  • CFU6