Informações da Disciplina

 Preparar para impressão 

Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação


Instituto de Matemática e Estatística
 
Ciência da Computação
 
Disciplina: MAC0695 - Combinatória II
Combinatorics II

Créditos Aula: 4
Créditos Trabalho: 0
Carga Horária Total: 60 h
Tipo: Semestral
Ativação: 01/01/2023 Desativação:

Objetivos
Aprofundar os conhecimentos obtidos na disciplina Combinatória I, através do estudo de resultados clássicos e contemporâneos que fazem uso de diversas técnicas combinatórias.
 
Deepen the study started in Combinatorics I, via the study of classical and modern results that make use of different combinatorial techniques.
 
 
Docente(s) Responsável(eis)
6901698 - Guilherme Oliveira Mota
88134 - Yoshiharu Kohayakawa
 
Programa Resumido
Nesta disciplina serão abordados teoria extremal dos conjuntos, tópicos avançados em teoria extremal dos grafos, teoria de Ramsey e método probabilístico, além de uma introdução ao método da regularidade e, opcionalmente, aos métodos da absorção e de contêineres.
 
This course will cover extremal set theory, advanced topics in extremal graph theory, Ramsey theory, and probabilistic methods, in addition to giving an introduction to the regularity method and possibly to the absorption and container methods.
 
 
Programa
Teoria extremal dos conjuntos: anticadeias, famílias intersectantes, Teorema de Kruskal e Katona.
Teoria extremal dos grafos: Teorema de Erdős e Stone, supersaturação para hipergrafos, limitantes para números cromáticos, números extremais. Teoria de Ramsey: teoria de Ramsey aditiva, números de Ramsey para grafos e hipergrafos. Método probabilístico: lema local de Lovász, desigualdades de Janson, escolha aleatória independente. Método da regularidade: lemas de regularidade e aplicações. Método da absorção: introdução ao método e aplicações. Método dos contêineres: conjuntos independentes em grafos e hipergrafos e aplicações.
 
Extremal set theory: antichains, intersecting families, Kruskal and Katona theorem. Extremal graph theory: Erdős and Stone's theorem, supersaturation for hypergraphs, bounds for chromatic numbers, extremal numbers. Ramsey theory: additive Ramsey theory, Ramsey numbers for graphs and hypergraphs. Probabilistic method: Lovász's local lemma, Janson's inequalities, independent random choice. Regularity method: regularity lemmas and applications. Absorption method: introduction to the method and applications. Container method: independent sets in graphs and hypergraphs and applications.
 
 
Avaliação
     
Método
Listas de exercícios
Critério
Média ponderada das notas nas listas
Norma de Recuperação
Não há recuperação. Justificativa: a avaliação será baseada em um volume substancial de exercícios ao longo do semestre, que terão o papel de levar ao amadurecimento do aluno na área da disciplina. Não é possível reproduzir algo parecido no processo de recuperação, que tem de ter lugar em um período muito curto.
 
Bibliografia
     
Bibliografia básica: 
1. F. Botler, M. Collares, T. Martins, W. Mendonça, R. Morris, G. Mota. Combinatória. Editora do IMPA, Rio de Janeiro, 2021. 315pp. ISBN: 978-65-89124-53-5. 
2. S. Janson, T. Luczak e A. Rucinski. Random graphs. Wiley-Interscience, New York, 2000. xii+333pp. ISBN: 0-471-17541-2. 
3. B. Bollobás. Random graphs. 2a. edição. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press,
Cambridge, 2001. xviii+498pp. ISBN: 0-521-80920-7; 0-521-79722-5. 
 

Clique para consultar os requisitos para MAC0695

Clique para consultar o oferecimento para MAC0695

Créditos | Fale conosco
© 1999 - 2024 - Superintendência de Tecnologia da Informação/USP