Colorações restritas de grafos aleatórios

Speakers: Guilherme Mota, USP.

Date: 28 apr 2021, 14h.

Place: Google Meet: meet.google.com/dra-gigp-gny.

Abstract: Dados grafos G, H_1 e H_2, denote por G ---> (H_1, H_2) a seguinte propriedade: em toda coloração das arestas de G há uma cópia monocromática de H_1 ou uma cópia "arco-íris" de H_2 (uma cópia de H_2 em que todas as arestas têm cores diferentes).

O número de Ramsey restrito, definido como o menor n tal que K_n ---> (H_1, H_2), existe se e somente se H_1 é uma estrela ou H_2 é uma floresta. Neste seminário vou determinar o "threshold" para a propriedade G (n, p) ---> (H_1, H_2) quando H_2 é uma floresta.

Este é um trabalho conjunto com Maurício Collares, Yoshiharu Kohayakawa e Carlos Gustavo Moreira.

 

Grupo de Thompson da Basílica

Speakers: Miguel Del Rio (doutor UNICAMP, 2019).

Date: 24 mar 2021, 16h.

Place: Google Meet: meet.google.com/dra-gigp-gny.

Abstract: O grupo de Thompson da Basílica, um grupo introduzido por Belk e Forrest em [2] e que tem relação com os grupos de Thompson F, T, V e muitos outros grupos com definições análogas a estes.

Nós estudaremos o problema da conjugação no grupo de Thompson da Basílica. Para isso vamos examinar a solução desse problema no grupo de Thompson T. Nossa solução usa uma técnica similar a aquela usada por Belk e Matucci em [3] com a vantagem de que achamos que pode ser usada em outros grupos como os grupos de rearranjos estudados por Belk e Forrest em [2].

[1] J. Belk and B. Forrest. A Thompson Group for the Basilica. Groups, Geometry, and Dynamics 9.4 (2015): 975–1000. doi:10.4171/GGD/333.

[2] J. Belk and B. Forrest. Rearrangement Groups of Fractals. Preprint (2015). arXiv:1510.03133.

[3] J. Belk and F. Matucci. Conjugacy and Dynamics in Thompson's Groups. Geometriae Dedicata 169.1 (2014): 239–261.

 

Propagação da COVID-19 usando medidas de centralidade de grafos

Speaker: Átila Arueira Jones, Inst. Federal do Sudeste de Minas Gerais.

Date: 02 dec 2020, 16h.

Place: Google Meet: meet.google.com/gbn-pvqf-bpw.

Abstract: Atualmente há uma grande preocupação na disseminação do vírus causador da doença COVID-19 e o distanciamento social ainda é a forma mais indicada para conter a propagação da doença. Neste trabalho modelamos a relação de alunos e professores de uma instituição de ensino através de um grafo para então simular a difusão do vírus, segundo o modelo epidêmico SIR. A propagação da epidemia foi observada tomando diferentes situações iniciais, a partir de um único vértice infectado inicial, de acordo com medidas de centralidade calculadas. Então observamos a influência dessas medidas na difusão do vírus e como isso está relacionado ao tempo do pico da epidemia.

Obs.: Trabalho em conjunto com Priscila R. Almeida (professora IFsudMG) e Luísa Gonçalves (graduando Engenharia Mecatrônica - IFsudMG).

 

On Undirected Two-commodity Integral Flow, Disjoint Paths and Strict Terminal Connection Problems

Speaker: Alexsander A. de Melo, COPPE-UFRJ.

Date: 30 sep 2020, 16h.

Place: Google Meet: meet.google.com/ost-kzem-mqk.

Abstract: Even, Itai and Shamir (1976) proved simple two-commodity integral flow is NP-complete both in the directed and undirected cases. In particular, the directed case was shown to be NP-complete even if one demand is unitary, which was improved by Fortune, Hopcroft and Wyllie (1980) who proved the problem is still NP-complete if both demands are unitary. The undirected case, on the other hand, was proved by Robertson and Seymour (1995) to be polynomial-time solvable if both demands are constant. Nevertheless, the complexity of the undirected case with exactly one constant demand has remained unknown. We close this forty year complexity gap, by showing the undirected case is NP-complete even if exactly one demand is unitary. As a by-product, we obtain the NP-completeness of determining whether a graph contains 1 + d pairwise vertex-disjoint paths, such that one path is between a given pair of vertices and d paths are between a second given pair of vertices. Additionally, we investigate the complexity of another related network design problem called Strict Terminal Connection.

Obs.: This is a joint work with Celina M. H. de Figueiredo (PESC/COPPE/UFRJ) and Uéverton dos Santos Souza (IC/UFF).

 

The monochromatic transversal game on clique-hypergraphs of powers of cycles

Speaker: Wilder P. Mendes, UFF.

Date: 26 aug 2020, 16h30.

Place: Google Meet: meet.google.com/ces-qqwf-coo.

Abstract: We introduce the monochromatic transversal game where the players, Alice and Bob, alternately colours vertices of a hypergraph. Alice, who colours the vertices with red, wins the game if she obtains a red transversal; and Bob wins if he does not let it happen, i.e. there exists a monochromatic blue hyperedge. Both players are enabled to start the game and they play optimally. We analyze the game played on clique-hypergraphs of complete graphs, paths, and powers of cycles. For each of these graphs, we show a strategy that allows one of the players to win the game.

Obs.: This joint work with Simone Dantas (IME/UFF), Sylvain Gravier (CNRS, Université Grenoble Alpes) and Rodrigo Marinho (IST, University of Lisbon, Portugal), was accepted for presentation and publication in the CTW 2020 (18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization).

Support:

http://printbiotec.uff.br/ 

www.antenabrasil.uff.br

https://www.facebook.com/antenabrasileiradematematica/ 

 

 

Mais artigos...

Pagina 3 de 6