B018796 - TEORIA DEI GRAFI E COMBINATORIA

Italiano

Introduzione alla teoria dei grafi: concetti fondamentali, grafi euleriani e hamiltoniani, alberi; grafi planari, grafi regolari, grafi bipartiti.Grafi diretti e connettivita'; reti e flussi. Colorazioni. Teoria di Ramsey.Teoria estremale degli insiemi.Teoria algebrica dei grafi.

Dispense del corso.
Graph Theory, R. Diestel.

Acquisire conoscenze su alcuni risultati di base delle teoria dei grafi e della combinatoria, cosi' come di alcune tecniche dimostrative usate in tali ambiti.

Corsi raccomandati: Algebra 1 e Algebra 2.

Numero di ore totali del corso: 225

Numero di ore per studio personale e altre attività formative di tipo individuale: 155

Numero di ore relative alle attività in aula: 70

Frequenza delle lezioni ed esercitazioni: Raccomandata
Strumenti a supporto della didattica UniFi E-Learning: http://e-l.unifi.it
Orario di ricevimento:
Martedi': 14.30-16.00
Giovedi': 14.00-15.30
Studio 39 - Dipartimento di Matematica e Informatica "U. Dini"

Prova orale

1. Concetti di base della Teoria dei Grafi.

Grafi e multigrafi. Isomorfismo di (multi)grafi.
Prime classi di grafi.
Grafo di Petersen. Sottografi e sottografi indotti. Grafi complementari.

Cammini; cammini semplici, circuiti, cicli.
Componenti connesse. Distanza.

Grafi hamiltoniani. Teoremi di Ore e di Dirac. Il grafo di Petersen non e' hamiltoniano.

Alcuni invarianti: distanza, diametro, indice di stabilita',
numero cromatico.

Problemi di Teoria Estremale dei grafi. Grafi $r$-partiti e grafi di Turan.
Teorema di Turan.

2. Alberi e grafi bipartiti. Accoppiamenti. 1-fattori.

Alberi e foreste. Spanning trees minimali.
Grafi bipartiti. Teoremi di Hall (dei matrimoni; SDR; SDR 'simultanei').
Teorema di Birkhoff-VonNeumann. Coperture. Teorema di Koenig.
Algoritmo ungherese. 1-fattori. Teorema di Tutte.
2-fattori; Teorema di Petersen. Grafi piani e planari.

3. Colorazioni

Grafi planari. Teorema di Kuratowski. Teorema dei 5 colori.
Colorazioni. Teorema di Brooks.
L-colorazioni. Teorema di Thomassen.
Grafi perfetti.

Colorazioni dei lati; indice cromatico. Teorema di Koenig.
Teorema di Vizing.

4. Reti e Flussi. Connettivita'

Grafi diretti; definizioni e proprieta' di base.
Reti e flussi. Teorema MaxFlow-MinCut.

Connettivita'. Teoremi di Menger.

5. Teoria algebrica dei grafi

Matrici di adiacenza; spettro. Operatore di Laplace.
Automorfismi di grafi. Grafi vertex-transitivi e edge-transitivi. Punti fissi di
automorfismi di alberi. Grafi di Calyey.

6. Teoria Estremale degli insiemi

Delta-sistemi e Lemma del girasole.
Intersecting families e ultrafiltri.
Principio dei cassetti; lemma di Dirichlet; Teorema di Schur
ed applicazioni.

Famiglie uniformi intersecanti. Teorema di Erdos-Ko-Rado.
Applicazioni alla geometria proiettiva finita.
Famiglie di Sperner.

Decomposizione di un insieme parzialmente ordinato come unione di catene / anticatene. Teorema di Dilworth.

7. Teoria di Ramsey

Numeri di Ramsey e loro limitazioni. Teoremi di Ramsey. Applicazioni.

Teoremi di Hales-Jewett e di Van der Waerden.