2º Workshop Brasileiro de Combinatória

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Caminhos hamiltonianos em hipergrafos

Nesta palestra nós vamos trilhar um caminho por vários tópicos de combinatória moderna. Falaremos de regularidade de Szemeredi em grafos, pseudo aleatoriedade, hipergrafos e caminhos hamiltonianos. O objetivo final é entender o aparecimento de caminhos
hamiltonianos em hipergrafos uniformemente densos, mas a palestra será formada de vários blocos auto contidos de informação.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Desigualdades de Concentração

Este minicurso tem como objetivo explorar diversos usos de desigualdades de concentração em combinatória. Ao longo de três aulas, exploraremos como limitar a probabilidade de variáveis aleatórias se desviarem de seus valores esperados, utilizando técnicas que não exigem o conhecimento exato da distribuição de probabilidade. Começaremos com a ferramenta mais básica, a desigualdade de Markov, analisando suas aplicações e as situações em que ela falha. Em seguida, veremos como a incorporação da variância nos leva à desigualdade de Chebyshev e, finalmente, exploraremos desigualdades como a de Hoeffding e a de Chernoff, que nos fornecem limitantes melhores em determinadas situações.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Desigualdades de Concentração

Este minicurso tem como objetivo explorar diversos usos de desigualdades de concentração em combinatória. Ao longo de três aulas, exploraremos como limitar a probabilidade de variáveis aleatórias se desviarem de seus valores esperados, utilizando técnicas que não exigem o conhecimento exato da distribuição de probabilidade. Começaremos com a ferramenta mais básica, a desigualdade de Markov, analisando suas aplicações e as situações em que ela falha. Em seguida, veremos como a incorporação da variância nos leva à desigualdade de Chebyshev e, finalmente, exploraremos desigualdades como a de Hoeffding e a de Chernoff, que nos fornecem limitantes melhores em determinadas situações.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Oportunidades de pós-graduação em Combinatória no Brasil e no mundo

Sala: SEM_SALA | Tipo: MESA_REDONDA

Induced path convexities on oriented graphs

In this work, for a given oriented graph D, we study its interval and hull numbers in the induced directed path and P3* convexities. We show that to calculate both parameters in the induced directed path convexity are NP-hard problems, when restricted to bipartite oriented graphs and DAGs, respectively. We also show some bounds and polynomial results for tournaments. Concerning this last class, we prove that determining its interval number in the P3* convexity belongs to W[2]-hard, when parameterized by the solution value.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

A Combinatória do Aprendizado: Dimensão VC e a conjectura RTD

Este minicurso introduz a Teoria do Aprendizado sob a ótica da Combinatória Extremal, desenhado para estudantes de Matemática, Ciência da Computação e áreas afins. O foco inicial será na Dimensão VC, uma medida clássica que quantifica a complexidade de uma família de funções binárias (ou classes de hipóteses), que possui aplicações diretas na Teoria do Aprendizado Estatístico. Abordaremos o conceito de "quebrar" um conjunto e demonstraremos o Lema de Sauer. Em seguida, introduziremos o conceito de testemunhas e a noção de Dimensão de Ensino Recursiva (RTD). Finalizaremos explorando a conjectura de Simon e Zilles, que propõe uma relação linear entre a RTD e a Dimensão VC. Também falaremos brevemente do Teorema Fundamental do Aprendizado Estatístico. O objetivo é fornecer ferramentas discretas essenciais para a compreensão dos limites teóricos dos algoritmos de classificação (como aqueles usados em Machine Learning).

Sala: SEM_SALA | Tipo: MINICURSO

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

A Combinatória do Aprendizado: Dimensão VC e a conjectura RTD

Este minicurso introduz a Teoria do Aprendizado sob a ótica da Combinatória Extremal, desenhado para estudantes de Matemática, Ciência da Computação e áreas afins. O foco inicial será na Dimensão VC, uma medida clássica que quantifica a complexidade de uma família de funções binárias (ou classes de hipóteses), que possui aplicações diretas na Teoria do Aprendizado Estatístico. Abordaremos o conceito de "quebrar" um conjunto e demonstraremos o Lema de Sauer. Em seguida, introduziremos o conceito de testemunhas e a noção de Dimensão de Ensino Recursiva (RTD). Finalizaremos explorando a conjectura de Simon e Zilles, que propõe uma relação linear entre a RTD e a Dimensão VC. Também falaremos brevemente do Teorema Fundamental do Aprendizado Estatístico. O objetivo é fornecer ferramentas discretas essenciais para a compreensão dos limites teóricos dos algoritmos de classificação (como aqueles usados em Machine Learning).

Sala: SEM_SALA | Tipo: MINICURSO

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Grupos de estudos

Sala: SEM_SALA | Tipo: MINICURSO

Hamilton cycles in sparse graphs: between randomness and symmetry

When does a graph G contain a Hamilton cycle? This is one of the central questions of graph theory, which is one of Karp’s original 21 NP-complete problems. In this talk, I’ll revise conditions on sparse graphs that ensure the existence of a Hamilton cycle. In particular, optimal pseudorandom conditions forcing not only Hamiltonicity, but also resilience and (approximate) Hamilton decompositions, and how symmetry also plays a role in the Hamiltonicity problem, as in the Lovász conjecture from 1969.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Desigualdades de Concentração

Este minicurso tem como objetivo explorar diversos usos de desigualdades de concentração em combinatória. Ao longo de três aulas, exploraremos como limitar a probabilidade de variáveis aleatórias se desviarem de seus valores esperados, utilizando técnicas que não exigem o conhecimento exato da distribuição de probabilidade. Começaremos com a ferramenta mais básica, a desigualdade de Markov, analisando suas aplicações e as situações em que ela falha. Em seguida, veremos como a incorporação da variância nos leva à desigualdade de Chebyshev e, finalmente, exploraremos desigualdades como a de Hoeffding e a de Chernoff, que nos fornecem limitantes melhores em determinadas situações.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Desigualdades de Concentração

Este minicurso tem como objetivo explorar diversos usos de desigualdades de concentração em combinatória. Ao longo de três aulas, exploraremos como limitar a probabilidade de variáveis aleatórias se desviarem de seus valores esperados, utilizando técnicas que não exigem o conhecimento exato da distribuição de probabilidade. Começaremos com a ferramenta mais básica, a desigualdade de Markov, analisando suas aplicações e as situações em que ela falha. Em seguida, veremos como a incorporação da variância nos leva à desigualdade de Chebyshev e, finalmente, exploraremos desigualdades como a de Hoeffding e a de Chernoff, que nos fornecem limitantes melhores em determinadas situações.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Grupos de estudos

Sala: SEM_SALA | Tipo: MINICURSO

Avan\c{c}os recentes em problemas do tipo Erd\H{o}s-Rothschild

O problema de Erdős-Rothschild é um problema da Combinatória Extremal motivado pelo problema de Turán. Na versão original de Erdős e Rothschild dos anos 70, dados um grafo F e um inteiro positivo r, o objetivo era determinar o grafo G com n vértices que admite o maior número de decomposições em até r subgrafos F-livres. Em outras palavras, o objetivo era determinar o grafo G com n vértices que admite o maior número de r-colorações de arestas tais que cada cor é F-livre. Nas últimas décadas, o problema foi estendido para colorações que evitam outros padrões de cores e para outras estruturas discretas. Nessa palestra, vou abordar os principais resultados e problemas em aberto sobre esse tema e, particularmente, dois resultados recentes. (Inclui resultados com
Hiep Han (Universidad de Santiago de Chile), Nícolas Moro Müller (UFRGS) e Dionatan Ricardo Schmidt (Unipampa)).

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

A Combinatória do Aprendizado: Dimensão VC e a conjectura RTD

Este minicurso introduz a Teoria do Aprendizado sob a ótica da Combinatória Extremal, desenhado para estudantes de Matemática, Ciência da Computação e áreas afins. O foco inicial será na Dimensão VC, uma medida clássica que quantifica a complexidade de uma família de funções binárias (ou classes de hipóteses), que possui aplicações diretas na Teoria do Aprendizado Estatístico. Abordaremos o conceito de "quebrar" um conjunto e demonstraremos o Lema de Sauer. Em seguida, introduziremos o conceito de testemunhas e a noção de Dimensão de Ensino Recursiva (RTD). Finalizaremos explorando a conjectura de Simon e Zilles, que propõe uma relação linear entre a RTD e a Dimensão VC. Também falaremos brevemente do Teorema Fundamental do Aprendizado Estatístico. O objetivo é fornecer ferramentas discretas essenciais para a compreensão dos limites teóricos dos algoritmos de classificação (como aqueles usados em Machine Learning).

Sala: SEM_SALA | Tipo: MINICURSO

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

A Combinatória do Aprendizado: Dimensão VC e a conjectura RTD

Este minicurso introduz a Teoria do Aprendizado sob a ótica da Combinatória Extremal, desenhado para estudantes de Matemática, Ciência da Computação e áreas afins. O foco inicial será na Dimensão VC, uma medida clássica que quantifica a complexidade de uma família de funções binárias (ou classes de hipóteses), que possui aplicações diretas na Teoria do Aprendizado Estatístico. Abordaremos o conceito de "quebrar" um conjunto e demonstraremos o Lema de Sauer. Em seguida, introduziremos o conceito de testemunhas e a noção de Dimensão de Ensino Recursiva (RTD). Finalizaremos explorando a conjectura de Simon e Zilles, que propõe uma relação linear entre a RTD e a Dimensão VC. Também falaremos brevemente do Teorema Fundamental do Aprendizado Estatístico. O objetivo é fornecer ferramentas discretas essenciais para a compreensão dos limites teóricos dos algoritmos de classificação (como aqueles usados em Machine Learning).

Sala: SEM_SALA | Tipo: MINICURSO

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Grupos de estudos

Sala: SEM_SALA | Tipo: MINICURSO

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Avanços recentes na teoria de Ramsey em grafos

Nessa palestra vamos apresentar um pouco sobre a teoria de Ramsey para grafos focando em resultados obtidos nos últimos anos. Em particular vamos falar das melhorias nas cotas inferiores para os números de Ramsey fora da diagonal, cotas superiores
para os números de Ramsey diagonais e números de Ramsey induzidos.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA

Sala: SEM_SALA | Tipo: ATIVIDADES_SOCIAIS

Desigualdades de Concentração

Este minicurso tem como objetivo explorar diversos usos de desigualdades de concentração em combinatória. Ao longo de três aulas, exploraremos como limitar a probabilidade de variáveis aleatórias se desviarem de seus valores esperados, utilizando técnicas que não exigem o conhecimento exato da distribuição de probabilidade. Começaremos com a ferramenta mais básica, a desigualdade de Markov, analisando suas aplicações e as situações em que ela falha. Em seguida, veremos como a incorporação da variância nos leva à desigualdade de Chebyshev e, finalmente, exploraremos desigualdades como a de Hoeffding e a de Chernoff, que nos fornecem limitantes melhores em determinadas situações.

Sala: SEM_SALA | Tipo: PALESTRA_PLENARIA