On applications of counting independent sets in hypergraphs
Palestrante: Jozsef Balogh (University of Illinois at Urbana-Champaign)
Onde e quando: Auditório NUMEC, sexta-feira 19/12 às 14:00.
Resumo:
Recently, Balogh-Morris-Samotij and Saxton-Thomason developed a method of counting independent sets in hypergraphs. In this talk, I shall show a recent application of the method, solving the following Erdős problem: What is the number of maximal triangle-free graphs?
Time permitting, I will survey some other recent applications.
These applications are partly joint with Das, Delcourt, Liu, Mycroft, Petrickova, Sharifzadeh and Treglown.
Uma breve introdução à teoria de complexidade parametrizada – Parte 3
Palestrante: Rafael Santos Coelho (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 12/12 às 14:00.
Resumo:
Nos dois primeiros seminários, abordamos algumas técnicas de projeto de algoritmos parametrizados, ou seja, métodos que nos permitem provar a tratabilidade por parâmetro fixo de um determinado problema. Neste terceiro e último seminário, seguiremos por um caminho complementar, isto é, discutiremos a questão da intratabilidade por parâmetro fixo. A pergunta central que pretendemos responder é: como provar que um problema não admite um algoritmo parametrizado para uma certa parametrização? Para isso, vamos introduzir o conceito de reduções parametrizadas e a chamada W-hierarquia e provaremos a completude de alguns problemas parametrizados naturais para os dois primeiros níveis dessa hierarquia. Se o tempo permitir, falaremos também sobre a conjectura Exponential Time Hypothesis e sobre como ela pode ser utilizada na obtenção de limitantes inferiores mais fortes para o tempo necessário para resolver alguns problemas parametrizados.
Uma breve introdução à teoria de complexidade parametrizada – Parte 2
Palestrante: Rafael Santos Coelho (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 31/10 às 14:00.
Resumo:
Neste seminário, vamos dar continuidade ao estudo de técnicas de projeto de algoritmos parametrizados. Em particular, discutiremos as técnicas conhecidas como compressão iterativa e coloração. A primeira delas foi proposta por Reed, Smith e Vetta em 2004 para o problema da transversal dos circuitos ímpares em grafos. Dada uma instância de um problema parametrizado e uma solução viável qualquer, em essência, a ideia da técnica consiste em sermos capazes de “comprimir” a solução dada, isto é, de encontrar uma nova solução de tamanho menor ou de concluir que a solução inicialmente fornecida é ótima. A técnica da coloração foi originalmente introduzida por Alon, Yuster e Zwick em 1995 e tem se mostrado bastante eficaz na abordagem de problemas em que buscamos encontrar em um dado grafo alguma subestrutura particular, por exemplo, um caminho ou um circuito de um determinado tamanho.
\(k\)-clustering de pontos se movimentando em uma reta
Palestrante: Marcio Takashi Iura Oshiro (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 24/10 às 14:00.
Resumo:
Dado \(n\) pontos que se movimentam com velocidade constante em uma reta, queremos particioná-los em \(k\) clusters tal que os clusters sejam “pequenos”. Essa partição é chamada de \(k\)-clustering.
O movimento de cada ponto define uma trajetória, que pode ser representada por um segmento de reta. Definindo o tamanho de um cluster como a área delimitada pelas trajetórias dos pontos desse cluster, podemos encontrar um \(k\)-clustering que minimiza a soma dos tamanhos de cada cluster em tempo polinomial.
Maximum number of colorings without monochromatic Schur triples
Palestrante: Hiệp Hàn (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 10/10 às 14:00.
Resumo:
We investigate subsets of finite abelian groups which maximize the number of \(r\)-colorings without monochromatic Schur triples, i.e. without monochromatic triples \((a,b,c)\) such that \(a+b=c\). We answer this question for groups of order \(|G| = 2 \pmod 3\) and \(r=2,3\) and for groups of even order and \(r=2,3,4,5\).
Joint work with Andrea Jimenez.
Tverberg strikes back
Palestrante: Günter M. Ziegler (Freie Universität Berlin)
Onde e quando: Auditório NUMEC, terça-feira 30/9 às 14:00.
Resumo:
“Tverberg’s Theorem” is a major result that the Norwegian Mathematian Helge Tverberg proved 60 years ago (freezing, in a hotel room in Manchester). Its “topological” version is a substantial extension, only partially proved up to now.
But why do we need a colored Tverberg’s Theorem? What should it say? Who proved it? And do you need heavy machinery for the proof? In this lecture I plan to discuss these questions, and offer some answers.
(Joint work with Pavle Blagojević, Florian Frick, and Benjamin Matschke.)
Uma breve introdução à teoria de complexidade parametrizada – Parte 1
Palestrante: Rafael Santos Coelho (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 26/09 às 14:00.
Resumo:
A teoria de complexidade parametrizada é um ramo da teoria de complexidade computacional que se dedica ao estudo da dificuldade de problemas tomando como referencial múltiplos parâmetros estruturais da entrada e não somente seu tamanho. Em essência, se por um lado a complexidade computacional clássica se interessa em saber quão difícil é um problema, a complexidade parametrizada busca entender o que de fato faz um problema ser difícil. Nesse seminário, o primeiro numa série de três, pretendemos discutir um pouco a história da evolução dessa área, apresentar conceitos básicos e mostrar duas técnicas de projeto de algoritmos parametrizados.
Como melhorar o algoritmo de Goemans e Williamson em dimensão fixa
Palestrante: Fernando Mário de Oliveira Filho (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 19/09 às 14:00.
Resumo
Usando programação semidefinida, Goemans e Williamson (1995) forneceram um algoritmo de aproximação para o problema do corte máximo com razão de aproximação 0.878…. Há uma família de grafos, de tamanhos cada vez maiores, que mostra que a razão de aproximação do algoritmo é justa, ou seja, que o integrality gap da relaxação semidefinida utilizada é exatamente 0.878…. O que ocorre, entretanto, se considerarmos a relaxação semidefinida para grafos de um determinado tamanho fixo?
Mostrarei que provar que, para grafos de tamanho fixo, o integrality gap da relaxação semidefinida é melhor que 0.878… é equivalente a mostrar que um corte máximo num certo grafo infinito cujos vértices são os pontos de uma esfera de dimensão fixa tem peso maior que o de um corte que divide a esfera em dois hemisférios.
Árvore Geradora de Comunicação Ótima
Palestrante: Santiago Ravelo (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 5/09 às 14:00.
Resumo
O problema da árvore geradora de comunicação ótima (Optimum Communication Spanning Tree Problem, OCT) foi introduzido por Hu em 1974. Nele são dados um grafo conexo \(G\), uma função de comprimento sobre as arestas de \(G\), \(w\colon E(G) \to \mathbb{Q}_+\), e uma função não-negativa de requerimento de comunicação entre todo par de vértices de \(G\), \(r\colon V(G) \times V(G) \to \mathbb{Q}\). O objetivo é encontrar uma árvore \(T\) geradora de \(G\) que minimize o somatório dos custos de comunicação entre todos os pares de vértices, onde o custo de comunicação entre os vértices \(u\) e \(v\) em \(T\) resulta: \((r(u,v)+r(v,u))d(T,u,v)\), sendo \(d(T,u,v)\) a distância entre \(u\) e \(v\) em \(T\) (isto é, a soma dos comprimentos das arestas no caminho em \(T\) entre \(u\) e \(v\)). O OCT é um problema NP-difícil inclusive quando os comprimentos satisfazem a desigualdade triangular e os requerimentos entre todo par de vértices são unitários. Nós estamos interessados no estudo deste problema e propomos algoritmos de aproximação polinomial para alguns casos particulares dele que também são NP-difíceis.
Decomposição de grafos altamente conexos em caminhos de tamanho 5
Palestrante: Guilherme Mota (IME-USP)
Onde e quando: Auditório NUMEC, sexta-feira 29/08 às 14:00.
Resumo:
Barát e Thomassen propuseram a seguinte conjectura sobre decomposição de grafos: para toda árvore \(T\), existe um inteiro positivo \(k\) tal que, se \(G\) é um grafo k-aresta-conexo e \(|E(T)|\) divide \(|E(G)|\), então \(G\) admite uma decomposição em cópias de \(T\). Essa conjectura foi verificada para estrelas, algumas biestrelas, caminhos de tamanho potência de 2 e caminhos de tamanho 3. Mostramos que essa conjectura vale para caminhos de tamanho 5.
Trabalho feito em conjunto com F. Botler, M. T. I. Oshiro e Y. Wakabayashi.
Flag Álgebras para Permutações
Palestrante: Leonardo Nagami Coregliano
Onde e quando: Auditório NUMEC, sexta-feira 22/08, às 14:00
Resumo:
Em 2007, Alexander A. Razborov desenvolveu a teoria de Flag Álgebras e utilizou-a para calcular a densidade mínima de triângulos de um grafo em função de sua densidade de arestas. A teoria de Flag Álgebras, porém, pode ser utilizada não somente para grafos, mas para diversos objetos combinatórios como hipergrafos, torneios, ordens parciais e permutações. A parte da teoria que vem ganhando maior destaque é o dito método semidefinido, através dele diversos autores conseguiram melhorar cotas e até resolver completamente vários problemas extremais difíceis.
Neste seminário, apresentaremos o problema de empacotamento de permutações, o que é uma Flag Álgebra para permutações e como usar seu método semidefinido para melhorar cotas do problema mencionado.
Quem é quem?
Palestrante: todos os membros do grupo!
Onde e quando: Auditório NUMEC, sexta-feira 15/08 às 14:00.
Resumo:
Cada aluno de pós-graduação, pós-doutorando e professor do grupo falará brevemente sobre seus interesses de pesquisa e estudos recentes.
Antonio Josefran de Oliveira Bastos:
Uma classe de problema muito estudada em combinatória consiste em estudar densidades máximas, ou mínimas, de substruturas em determinadas estruturas, e.g, a densidade máxima de triângulos em grafos livres de grafos completos de tamanho 4. Em permutações, estudar a densidade máxima de uma permutação em permutações de tamanho fixo é conhecido como problema de empacotamento. Nosso objetivo é estudar o problema de empacotamento para algumas classes de permutações.
Luis Eduardo Zambrano Fernandez
Marcio Takashi Iura Oshiro:
Estudo problemas de clustering com pontos em movimento. Em problemas de clustering queremos particionar o conjunto de pontos em subconjuntos, clusters, tal que os clusters sejam “pequenos” de acordo com alguma medida. No modelo que estou estudando atualmente, os pontos estão em uma reta e têm velocidade constante para a direita ou para a esquerda. Ao longo do tempo, as trajetórias desses pontos formam segmentos de retas e o problema se reduz a particionar segmentos de retas. A medida considerada é a área da região limitada pelos segmentos do cluster. Entre as funções objetivos consideradas estão minimizar a soma das áreas de cada cluster e minimizar a maior área de um cluster.
Roberto Freitas Parente:
Em combinatória extremal assintótica estamos, em geral, interessados em estudar o comportamento assintóticos de densidades entre duas estruturas combinatórias (grafos, digrafos, hipergrafos, etc). No momento, estou trabalhando com teoria de flag álgebras desenvolvida por A. Razborov que, através de intersecções das estruturas combinatórias, constrói-se uma álgebra comutativa e um cálculo em cima desta. Um objeto importante desta teoria é o que denotamos por homomorfismos positivos entre a flag álgebra e o conjunto dos reais. Definiremos o que são esses homomorfismos positivos.