MAC5775 Métodos Probabilísticos em Combinatória e em Teoria da Computação I
[Edição do 1o. Semestre de 2018]
(Página eternamente minimal e em mutação)
Sinopse das aulas
Março
- Aula introdutória. Assuntos administrativos. Provas por contagem. Funções booleanas, propriedade B
- Espaços de probabilidade finitos. Exemplos. O problema do empregador
- Variáveis aleatórias e esperança. Exemplos
- Um problema geométrico. Número médio de comparações do quicksort
- Mais aplicações do primeiro momento. O teorema de Szemerédi e Trotter via número de cruzamentos
- Consequências do teorema de Szemerédi e Trotter. Quicksort (cont.)
- Semana Santa
- Semana Santa
Abril
- Método do segundo momento; teorema de Hardy e Ramanujan
- Subgrafos pequenos em \(G(n,p)\)
- A conjectura de Erdős e Hanani e o teorema de Rödl. O teorema de Frankl, Rödl e Pippenger
- Prova do teorema de Frankl, Rödl e Pippenger
- Folga (professor fora de São Paulo)
- Folga (professor fora de São Paulo)
- Prova do teorema de Frankl, Rödl e Pippenger: prova do Nibbling Lemma
- Probabilidades exponencialmente pequenas; conjuntos agudos exponenciais
- Recesso escolar
Maio
- Semana de break
- Probabilidades exponenciais: algumas provas. A desigualdade FKG–Harris. Desigualdades de Janson
- Desigualdade de Janson (cont.). A desigualdade de McDiarmid
- Número cromático de \(G(n,p)\): teorema de Bollobás
- Teorema de Bollobás via a desigualdade de McDiarmid. Concentração do número de clique e do número cromático
- Concentração do número cromático (cont.). Martingais
- Martingais e a desigualdade de McDiarmid
- Semana de break
- Semana de break
Junho
- O lema local. Circuitos pares em grafos dirigidos
- Circuitos \(\equiv0\pmod k\) em grafos dirigidos. Versão algorítmica do lema local (Moser–Tardos)
- Moser–Tardos (cont.)
- Complexidade de circuitos e o teorema de Razborov
- Teorema de Razborov (cont.). Circuitos de profundidade limitada
- Circuitos de profundidade limitada (cont.)
- Circuitos de profundidade limitada (cont.)
- FIFA World Cup
Julho
- Circuitos de profundidade limitada (cont.). Exercícios
- Exercícios
Página principal de MAC5775, 1o. semestre de 2018