Jogo Mapa do Tesouro

Speaker: Andressa Martins Moraes, UFRJ/PPGI/AMN.

Date: 30 sep 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste seminário apresentarei o Jogo Mapa do Tesouro, um jogo em grafos aplicado na educação com objetivo de avaliar o desenvolvimento da aprendizagem utilizando conceitos da neurociência e empregando uma estrutura baseada em grafos.

 

The size-Ramsey number of powers of bounded degree trees

Speaker: Taísa Martins, IMPA.

Date: 28 aug 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Given a positive integer s, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges where in any s-colouring of E(G) there is a monochromatic copy of H. We prove that, for any positive integers k and s, the s-colour size-Ramsey number of the kth power of any n-vertex tree is linear on n.

This is a joint work with S. Berger, Y. Kohayakawa, G. S. Maesaka, W. Mendonça, G. O. Mota and O. Parczyk.

 

Dificuldade e Eficiência de Problemas em Grafos, Strings e Permutações

Speaker: Luis Felipe Ignácio Cunha, IME-UFF.

Date: 21 aug 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste seminário, trataremos de problemas em grafos, strings e permutações. Estes problemas são desafiadores do ponto de vista combinatório e possuem muitas questões intrigantes há anos. Apresentaremos nosso avanços nos estudos abaixo.

-- Admissibilidade: desejamos obter num grafo G o menor inteiro t, tal que exista uma árvore geradora T cuja distância em T entre cada par de vértices vizinhos de G seja no máximo t;
-- Tesselabilidade: uma tesselação de um grafo G é uma partição do conjunto de vértices em cliques. Desejamos obter o menor t, tal que existam t tesselações cuja união das tesselações cubra o conjunto das arestas do grafo;
-- Blocos haplótipos: dadas k strings binárias, desejamos obter todas subsequências maximais cujos elementos em cada coluna sejam iguais.
-- Indexação de strings: desejamos preprocessar uma string binária de modo a responder em tempo constante se há uma substring de tamanho k com i cópias de 1s, para valores arbitrários de k e i;
-- Distância, Diâmetro, Centralidade, Mediana e Convexidade em permutações: estes são problemas associados a grupos simétricos de permutações, que possuem muitas aplicações em biologia matemática, cujo intuito é compreender melhor a filogenia de espécies.
Além de estudos obtidos nesses temas, serão apresentadas as colaborações em pesquisa e atividades de ensino e extensão em desenvolvimento.

 

Sobre coloração total equilibrada de grafos multipartidos completos balanceados

Speaker: Anderson G. da Silva, Universidade de Delaware.

Date: 26 jun 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: Uma coloração total é a aplicação de cores aos vértices e arestas de um grafo de modo que elementos adjacentes ou incidentes recebam cores distintas. O número cromático total de um grafo é o menor inteiro positivo para o qual o grafo possui coloração total. Dada uma coloração total, se a diferença entre as cardinalidades de quaisquer duas classes de cor for no máximo um, então dizemos que a coloração é equilibrada e o menor número inteiro positivo que satisfaz essa condição é dito o número cromático total equilibrado do grafo. Para tal valor, Wang (2002) conjecturou um limite superior. Um grafo multipartido completo balanceado é aquele em que o conjunto de vértices pode ser particionado em conjuntos independentes com a mesma quantidade de vértices, sendo adjacentes quaisquer dois vértices de diferentes partes da partição. Determinamos o número cromático total equilibrado dos grafos multipartidos completos balanceados, contribuindo, desta forma, com novos resultados na área de coloração de grafos.

Trabalho em conjunto com Diana Sasaki (UERJ) e Simone Dantas (UFF).

 

A general method for forbidden induced subgraph sandwich problem NP-completeness

Speaker: Rafael Bernardo Teixeira, ICE-UFRRJ.

Date: 29 apr 2019, 13h.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

Abstract: We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic and Shamir (1993), with respect to classes of graphs defined by excluding induced subgraphs. The Π graph sandwich problem asks, for a pair of graphs G1 = (V, E1) and G2 = (V, E2) with E1 ⊆ E2, whether there exists a graph G = (V, E) with E1 ⊆ E ⊆ E2 that satisfies property Π. We consider the property of being H-free, where H is a fixed graph. Using a new variant of the SAT problem, we present a general framework to establish the NP-completeness of the sandwich problem for several H-free graph classes which generalizes the previous strategy for the class of Hereditary clique-Helly graphs. We also provide infinite families of 3-connected special forbidden induced subgraphs for which each forbidden induced subgraph sandwich problem is NP-complete.

Obs.: Joint work with Simone Dantas (UFF), Celina M. H. de Figueiredo (COPPE-UFRJ) and Priscila Petito (UERJ).

 

Controlabilidade de Fronteira Livre para Equação do Calor 1D com Não-linearidades Locais e Não-locais

Speaker: Vitor Costa, IME-UERJ.

Date: 27 mar 2019, 14h.

Place: Room 411, Bloco H, Campus Gragoatá, UFF.

Abstract: Neste trabalho apresentamos o problema de controle com fronteira livre para equações do calor não-lineares 1D com um controle local atuando na variável espacial. O principal resultado mostra que, se o dado inicial é suficientemente pequeno, então a solução do sistema é conduzida a zero no tempo t=T.

 

Women in Science

Speaker: Luise-Charlotte Kappe, Binghamton University.

Date: 27 feb 2019.

Place: Room 407, Bloco H, Campus Gragoatá, UFF.

11:30h: Finite coverings: a journey through groups, loops, rings, and semigroups.

14h: It's a wonderful life! - Reflections on a career as a mathematician.

Mulheres na Ciência 2