PICME Combinatória e Probabilidade

Professores:

• Yoshiharu Kohayakawa — yoshi@ime.usp.br
• Miguel Natalio Abadi — leugim@ime.usp.br

1°. semestre de 2013

Tópicos das reuniões

• 12/03/2013 (por Giulia Maesaka) Programação Linear (PL): introdução, exemplos, programação inteira (PI)
• 19/03/2013 (por GM) Programação Linear: aproximação de PI usando PL
• 02/04/2013 (por GM) Programação Linear: forma equacional das restrições; soluções básicas e interpretação geométrica (hiperplanos, poliedros, fecho convexo e vértices)
• 09/04/2013 (por Eric Endo) Programação Semidefinida: Revisão de álgebra linear: matriz hermitiana, menor simétrico, autovalores, matriz semidefinida positiva, cone convexo; teorema de separação de Hahn-Banach
• 23/04/2013 (por EE) Programação Semidefinida: lema de Farkas (versão fraca e versão de inferência); dualidade em programação linear (PL); teorema da dualidade forte e teorema das folgas complementares; exemplo: politopos dos conjuntos estáveis
• 31/04/2013 (por EE) Programação Semidefinida: politopos dos conjuntos estáveis (continuação), conjecturas fraca e forte dos grafos perfeitos
• 07/05/2013 (por EE) Programação Semidefinida: problema de programação semidefinida; propriedades; o problema dual
• 21/05/2013 (por EE) Capacidade de Shannon para Grafos: formulação, produto forte em grafos, representação ortonormal de grafos, guarda-chuva de Lovász (Lovász' umbrella)
• 28/05/2013 (por EE) Função Theta de Lovász $\vartheta(G)$: algumas propriedades
• 28/05/2013 (por EE) Função Theta de Lovász $\vartheta(G)$: propriedades (continuação I) — relações com representações ortonormais e matrizes positivas semidefinidas
• 11/06/2013 (por EE) Função Theta de Lovász $\vartheta(G)$: propriedades (continuação II) — relações com representações ortonormais e STAB$(G)$, STAB$(G)$ STAB$(G)$; teorema sanduíche (clique máxima, função Theta de Lovász e número cromático): $\omega(G)\leq\vartheta(G)\leq\chi(G)$
• 18/06/2013 (por Leonardo Coregliano) Conjectura de Erdős–Simonovits–Sidorenko: homomorfismos de grafos; epaços mensuráveis;desigualdade de Jensen (esperança de função convexa); acoplamentos independentes
• 25/06/2013 (por LC) Conjectura de Erdős–Simonovits–Sidorenko: acoplamentos independentes (continuação)

Notas dos encontros

Notas 2013: (código fonte) — (pdf)

Data	Descrição
2013-06-20	notas reunião 18/jun até espaços mensuráveis
2013-06-19	esboço das notas da reunião dia 18/jun
2013-06-13	mais demonstrações da reunião 11/jun
2013-06-13	correções enviadas pelo Eric
2013-06-13	updates reunião 11/jun
2013-06-11	notas da reunião 11 junho
2013-06-11	sugestões e correções do Eric

Para Eric e Leonardo, todo's.