MCZA037-17 - Combinatória Extremal Segundo Quadrimestre de 2024

Avisos importantes

  • 🆕 11/07 - Horário de atendimento foi atualizado
  • 🆕 11/07 - Enunciado do exercício 1 da Lista 2 foi corrigido (Listas)
  • 🆕 11/07 - Datas das avaliações foram definidas
  • 🆕 08/07 - Listas 2 liberada
  • 03/07 - Lista 1 liberada
  • 03/07 - Typos foram corrigidos nas notas de aula sobre o Teorema de Turan (Notas de Aula)
  • 23/06 - Com o fim da greve, o nosso curso começará no dia 25/06.
  • 02/06 - Página no ar.

Objetivos

Introduzir o aluno à combinatória extremal.

Ementa da disciplina

Teoria Extremal de Conjuntos: famílias intersectantes, Teorema de Sperner, Teorema Erdos-Ko-Rado, Teorema de Ahlswede e Khachatrian, Desigualdades FKG. Teoremas de Ramsey, Limitantes para números de Ramsey, Teoremas de Ramsey para Grafos, Versão infinita do Teorema de Ramsey, Teoremas de van der Waerden e Schur.

Recomendações

Disciplinas: Matemática Discreta

Para facilitar o acompanhamento do curso é recomendado que você possua:

  • familiaridade com linguagem matemática (como quantificadores lógicos, somatórios e manipulação algébrica).
  • familiaridade com métodos de demonstrações matemáticas.

Outros materiais de apoio:

Bibliografia e outros materiais

  1. [BCM4] Botler, F.; Collares, M.; Martins, T.; Mendonça, W.; Morris, R. Mota, G. Combinatória. 1st ed. IMPA. 2022.
  2. [CLRS2] Jukna, S.; Extremal Combinatorics - With Applications in Computer Science. 2nd ed. Springer Press. 2011.
  3. Colinha

Critérios de avaliação regular

A média final antes da REC ( MF ) será calculada da seguinte forma:

\[ MF = 0.5 * P1 + 0.5 * P2, \]

onde

  • P1 e P2 são as notas da primeira e segunda avaliações, respectivamente.

\[ CF = \begin{cases} \textbf{A} ,& \text{se } MF \in [8.5;10.0]\\ \textbf{B} ,& \text{se } MF \in [7.0;8.5) \\ \textbf{C} ,& \text{se } MF \in [6.0;7.0) \\ \textbf{F} ,& \text{se } MF < 5.0\\ \textbf{O} ,& \text{se o número de faltas exceder 25% do total de aulas (independente do valor MF)} \end{cases} \]

🚨 Caso seja verificado ocorrência de fraude acadêmica, o aluno será automaticamente reprovado com F.

Mecanismo de recuperação

  • A recuperação será aplicada apenas aos alunos que obtiveram conceito final D ou F .
  • Consistirá numa avaliação, cujo conteúdo englobará todos os temas vistos durante o quadrimestre.
  • A nota obtida na avaliação de recuperação (NR) será usada para obter a nota final com recuperação (NFR), que consiste na média:

\[NFR = \frac{MF + NR}{2} \]

  • O conceito final com recuperação (CFR) será calculado da seguinte maneira:

\[ CFR = \begin{cases} C, & \text{se } CF = D \text{ e } NFR \geq 6;\\ D, & \text{se } CF = D \text{ e } NFR < 6;\\ D, & \text{se } CF = F \text{ e } NFR \geq 5;\\ F, & \text{caso contrário}. \end{cases} \]

Dias, horários e locais das aulas

  • Terças-feiras: 19h - 21h (sala S-307-3).
  • Quintas-feiras: 21h - 23h (sala S-307-3).

Datas Importantes

  • P1: 06/08 (Terça-feira)
  • P2: 17/09 (Terça-feira)
  • Substitutiva: 19/09 (Quinta-feira)
  • REC: 05/10 às 10h (Sábado)

Avaliação substitutiva está disponível apenas para os casos assegurados pelo regulamento da UFABC.

Atendimento

Local: Bloco A, Torre 2, Piso 5, Sala 518-2

  • Horário: Quintas-feiras das 18h às 19h.

Cronograma

Aula Data Tópico Seções (\(BCM^4\))
01 25/06 Princípios e técnicas básicas em combinatória 1.*
02 27/06 Princípios e técnicas básicas em combinatória 1.*
03 02/07 Números extremais, Teorema de Mantel 3.0 e 3.1
04 04/07 Teorema de Turán 3.0 e 3.1
05 11/07 Números extremais de grafos bipartidos 3.2
06 16/07 Números extremais de árvores 3.2.1
07 18/07 Supersaturação e estabilidade 3.3, 3.4
08 23/07 Teorema de Ramsey; Variações dos números de Ramsey 4.0, 4.1
09 25/07 Um limitante inferior para o número de Ramsey; Teoria de Ramsey em Grafos 4.1
10 30/07 Número de Ramsey do Pk; Espaços de probabilidade 4.3
11 01/08 Número de Ramsey do Pk; Espaços de probabilidade 4.3
12 06/08 Avaliação 1  
13 08/08 Método probabilístico; Eventos independentes 5.0, 5.1, 5.2
14 13/08 Método do primeiro momento 5.3
15 15/08 Método da alteração; Desigualdade de Markov 5.4, 5.5
16 22/08 Método do segundo momento; Método do segundo momento 5.6
17 27/08 Método da concentração, desigualdade de Chernoff 5.7
18 29/08 Número tamanho Ramsey de caminhos; Grafos aleatórios 6.0, 6.1
19 03/09 Números extremais de ciclos pares; Conexidade de G(n,p) 6.2, 6.3
20 05/09 Números extremais de ciclos pares; Conexidade de G(n,p) 6.3, 6.4
21 10/09 Funções limiares; Subgrafos pequenos; Teoria de Ramsey em G(n,p) 6.5
22 12/09 Subgrafos pequenos; Teoria de Ramsey em G(n, p) 6.6
23 17/09 Avaliação 2  
24 19/09 Sub P1 e P2  

Listas