Combinatória II

1- Teoria de Ramsey: teoremas de van der Waerden, Rado e Hales-Jewett; números de Ramsey de grafos com grau limitado, cotas para números de Ramsey diagonais, fora da diagonal e de hipergrafos. Progresso recente em teoria de Ramsey para grafos.
2. O método probabilístico: a componente gigante, o número cromático de G(n,p), o lema local, o nibble de Rodl, processos aleatórios de grafos, desigualdades de concentração, escolha aleatória dependente.
3. Métodos algébricos e topológicos: o método polinomial (o nullstellensatz combinatorial, a conjectura de Kakeya em corpos finitos); a desigualdade modular de Frankl-Wilson e aplicações (refutação da conjectura de Borsuk, cotas inferiores construtivas para números de Ramsey, o número cromático do plano); aplicações do teorema de Borsuk-Ulam.
4. Combinatória aditiva: conjuntos-soma (teoremas de Cauchy-Davenport e Freiman), teorema de Balog-Szemerédi-Gowers, conjuntos sem somas (conjectura de Cameron-Erdos), o teorema de Roth, discussão a respeito do teorema de Szemerédi.
5. O método de containers para hipergrafos: problemas extremais e Ramsey em G(n,p), contagem e estrutura típica dos grafos sem cópias de H, números de Folkman, números de Ramsey induzido, construções em geometria discreta. 

Referências:
[1] N. Alon and J. H. Spencer. – The probabilistic method, 3a edição, Wiley, New York, 2008.
[2] L. Babai and P. Frankl. – Linear algebra methods in combinatorics, Departament of Computer Science, University of Chicago, versão preliminar, 1991.
[3] B. Bollobás. – Modern Graph Theory (Graduate Texts in Mathematics), Springer-Verlag, New York, 1998.
[4] J. Matousek. – Thirty-three miniatures (mathematical and algorithmic applications of linear algebra), AMS, 2010.
[5] T. Tao and V. Vu. – Additive combinatorics, Cambridge Studies in Advanced Mathematics, CUP, 2006.
 
* Ementa básica. O professor tem autonomia para efetuar qualquer alteração.