Lezione 1 (mercoledí 11 Novembre, 14:00)
Liner algebra bound: una ricetta per dire quanto è il massimo numero di oggetti con una certa proprietà.
Criterio della diagonale: un modo semplice per dire che certe cose sono linearmente indipendenti.
Lucidi (i lucidi sono in OpenOffice )
Lezione 2 (mercoledí 18 Novembre, 14:00)
Alcuni "rompicapi geometrici" e come
Dehn risolve il terzo problema di Hilbert.
Secondo me la soluzione di Dehn ci suggerisce:
Una ricetta per dimostrare che due oggetti non sono "riducibili"
l'uno all'altro.
Lucidi
Lezione 3 (mercoledí 2 Dicembre, 14:00)
Il concetto di vettori in "posizione generica" e come generarli.
Come utilizzarli per "tradurre" le intersezioni di insiemi in polinomi (dimostrazione del Teorema di Bollobás).
Lucidi
Lezione 4 (mercoledí 13 Gennaio, 15:00)
Il rompicapo di oggi riguarda la copertura di grafi completi tramite grafi bipartiti. Dalla soluzione dovremmo capire queste due cose:
Guardiamo al rango di una matrice come un indice della sua "complessitá".
Una ricetta per dire il minimo numero di "pezzi" necessari per ottenere un certo oggetto.
Lucidi
Lezione 5 (venerdí 15 Gennaio, 15:00)
Se un oggetto è "grande abbastanza" comunque lo colori c'è sempre un "blocco" con un solo colore.
Abbiamo visto due teoremi di questo tipo: Teorema di Ramsey (coloro un grafo) e Teorema di Schur (coloro i numeri). Abbiamo visto due cose:
Teorema di Ramsey implica quello di Schur.
Cosa significa "grande abbastanza" per il Teorema di Ramsey:
per ora abbiamo un limite inferiore polinomiale ed uno superiore esponenziale.
Lucidi
Lezione 6 (mercoledí 27 Gennaio, 15:00)
Risponderemo alla domanda rimasta aperta la lezione precedente.
Ci serve un "buon" modo per colorare i grafi. Abbiamo visto due cose:
Otteniamo una colorazione da limitazioni su insiemi con intersezioni "limitate".
Disuguaglianza di Fisher dimostrata con una variante del criterio della diagonale.
Il tutto segue dalla prima ricetta vista nella prima lezione (linear algebra bound ).
Lucidi
Lezione 7 (mercoledí 17 Febraio, 15:00)
Costruzione esplicite di grafi di Ramsey e ingredianti utili:
I polinomi linearmente indipendenti su F2 sono "pochi".
Due teoremi su insiemi con intersezioni "a pochi valori".
Il primo punto segue dalla ricetta vista nella prima lezione (linear algebra bound ) ed implica il secondo punto.
Lucidi
Lezione 8 (mercoledí 17 Marzo, 15:00)
Linear Algebra + Metodo Probabilistico ==> Lower Bound Complessitá Circuitale
I polinomi di grado basso non possono calcolare (bene) la funzione soglia (Linear Algebra).
I circuiti di profonditá costante sono (essenzialmente) dei polinomi di grado basso (Metodo Probabilistico).
Cosí Razborov dimostra il lower bound esponenziale su circuiti di profonditá costante per calcolare la semplice funzione soglia!
Lucidi
Lezione 9 (mercoledí 21 Aprile, 17:00)
La parte probabilistica della lezione precedente
(polinomi che approssimano i circuiti).
lezione precedente
Lezione 10 (mercoledí 5 Maggio, 15:00)
Convessitá e Teorema di Helly,
altri esempi di teoremi "dello stesso tipo":
Una condizione "locale" implica una "globale"
Una variante per insiemi
Lucidi (versione pdf )
Lezione 11 (giovedí 13 Maggio??, ??:00)
Teoremi di "tipo Helly" per insiemi (il vero significato del Teorema di Bollobás ) e per formule Booleane.