MAC5775 Métodos Probabilísticos em Combinatória e em Teoria da Computação I

• [2020-08-31 Mon] Aula introdutória. Assuntos administrativos. Provas por contagem. Funções booleanas, propriedade B, corte máximo em grafos

• [2020-09-02 Wed] Elementos da teoria de probabilidade e algumas aplicações
• [2020-09-09 Wed] Subconjuntos aleatórios, monotonicidade, funções limiares, teorema de Bollobás e Thomason
• [2020-09-14 Mon] Funções limiares para progressões aritméticas e para subgrafos de \(G(n,p)\)
• [2020-09-16 Wed] Funções limiares para subgrafos de \(G(n,p)\) (cont.). Desigualdade de Chebyshev e concentração. Teorema de Hardy e Ramanujan (enunciado)
• [2020-09-21 Mon] A prova de Turán do teorema de Hardy e Ramanujan
• [2020-09-23 Wed] Grafos com número cromático e cintura grandes; propriedade B revisitada
• [2020-09-28 Mon] Propriedade B (cont.). O método da alteração. Uma conjectura de Thomassen
• [2020-09-30 Wed] Rödl nibble e a conjectura de Erdős e Hanani. O teorema de Frankl, Rödl, Pippenger e Füredi (FRPF)

• [2020-10-05 Mon] Prova do teorema FRPF
• [2020-10-07 Wed] Prova do teorema FRPF (cont.)
• [2020-10-12 Mon] Feriado
• [2020-10-14 Wed] Aula cancelada
• [2020-10-19 Mon] O princípio da inclusão e exclusão e as desigualdades de Bonferroni
• [2020-10-21 Wed] A heurística de Poisson; vértices isolados em \(G(n,p)\). Probabilidade conexidade de \(G(n,p)\)
• [2020-10-26 Mon] O lema local
• [2020-10-28 Wed] O lema local (cont.). Arboricidade linear

• [2020-11-02 Mon] Feriado
• [2020-11-04 Wed] Arboricidade linear (cont.). Probabilidades exponencialmente pequenas; cotas de Chernoff
• [2020-11-09 Mon] Probabilidades exponencialmente pequenas (cont.). Cotas de Chernoff para v.as binomiais
• [2020-11-11 Wed] Probabilidades exponencialmente pequenas (cont.). O método das diferenças limitadas
• [2020-11-16 Mon] Probabilidades exponencialmente pequenas (cont.). A desigualdade de Janson
• [2020-11-18 Wed] A desigualdade de Janson (cont.). O número cromático de \(G(n,p)\)
• [2020-11-23 Mon] O número cromático de \(G(n,p)\) (cont.)
• [2020-11-25 Wed] Uniformidade da distribuição das arestas de \(G(n,p)\)
• [2020-11-30 Mon] Grafos expansores e o teorema de Friedman e Pippenger sobre árvores em expansores

• [2020-12-02 Wed] Teorema de Friedman e Pippenger (cont.). Árvores de tamanho moderado em \(G(n,p)\)
• [2020-12-07 Mon] Elementos da teoria espectral dos grafos; \((n,d,\lambda)\)-grafos e o Expander Mixing Lemma
• [2020-12-09 Wed] Passeios aleatórios em expansores; confinamento de passeios; economia de aleatoriedade
• [2020-12-14 Mon] Discussão de exercícios
• [2020-12-16 Wed] Discussão de exercícios

Página principal de MAC5775, 2o semestre de 2020