Tema:Big Line Big Clique conjecture e bloqueadores de visibilidade
Gabriel Kuribara Lasso orientado por Carlos Eduardo Ferreira
Dado um conjunto P de pontos no plano, podemos definir o grafo de visibilidade desses pontos, colocando uma aresta entre dois pontos de P se, e somente se não houver nenhum ponto de P no segmento aberto que liga esses dois pontos. É natural pensar que para conjuntos grandes com poucos pontos colineares o número de clique do grafo de visibilidade associado seja alto. Essa é uma questão em aberto, conhecida como conjectura big-line-big-clique, que deu origem a algumas pesquisas interessantes na área.
Palavras-chave: grafos, grafos-de-visibilidade, geometria-combinatória, teoria-de-ramsey.
Faremos um estudo de um problema geométrico ligado a teoria de Ramsey. Tal problema foi colocado em 2005 por Jan Kára, Attila Pór e David R. Wood enquanto estudavam o número cromático de grafos de visibilidade. O problema pode ser colocado da seguinte forma: "Quão grande deve ser um conjunto de pontos para que ele conhtenha l pontos colineares ou k pontos visíveis dois a dois?".
Uma observação sobre esse problema é que se dois pontos não são visíveis, então existe um terceiro que bloqueia a visibilidade deles. Outro problema estudado aqui é sobre o tamanho mínimo do conjunto de bloqueadores para um conjunto de pontos.
Versão mais recente no GitHub