Combinatória II

1- Teoria de Ramsey: Teorema 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, número cromático de G(n, p), o lema local, nibble de Rodl, processos aleatórios de grafos, desigualdades de concentração, discrepância (seis desvios-padrão bastam, teorema de Beck-Fiala), 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), prova do teorema de Roth, discussão a respeito do teorema de Szemerédi.
5. O método de containers para hipergrafos: Erdos-Stone em G(n; p), o teorema de Szemerédi esparso, problemas do tipo Ramsey em G(n; p), contagem e estrutura típica dos grafos sem cópias de H.
 
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. Bollogá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.