PPGCCM PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO FUNDAÇÃO UNIVERSIDADE FEDERAL DO ABC Telefone/Ramal: Não informado http://propg.ufabc.edu.br/ppgccm

Banca de DEFESA: JULIANE KRISTINE DE LIMA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : JULIANE KRISTINE DE LIMA
DATA : 14/09/2022
HORA: 15:00
LOCAL: https://meet.google.com/zox-cazs-izq
TÍTULO:

Cobertura de grafos aleatórios em componentes monocromáticas


PÁGINAS: 20
RESUMO:

Muitos problemas de particionamento e cobertura dos vértices de um
grafo estão em aberto, ainda que estejam presentes na literatura há
mais de 50 anos. Neste trabalho, o interesse está em determinar o
menor número $t$ de componentes monocromáticas necessárias para cobrir
os vértices de um grafo aleatório binomial em qualquer coloração de
arestas com $r=3$ cores, propriedade denotada por $tc_r(G(n,p)) \leq
t$. No caso de $G(n,p)$, em que a densidade de arestas varia em função
de $p=p(n)$, o objetivo deste trabalho é investigar o valor de $p$ que
caracteriza uma função limiar para a propriedade $tc_3(G(n,p)) \leq
3$. Bal e De Biasio propuseram esse problema em 2017 e, desde então,
alguns trabalhos trouxeram avanços no entendimento da propriedade. Por
meio da construção de um contraexemplo, Ebsen Mota e Schnitzer
determinaram um limitante inferior para $tc_r(G(n,p)) \leq t$, que
ocorre assintoticamente quase certamente com $p \ll \left(\frac{\log
n}{n}\right)^{1/4}$. Em 2021, Brada\v{c} e Buci\'{c} determinaram
como limitante superior para a mesma propriedade o valor de $p \gg
\left(\frac{\log n}{n}\right)^{1/4}$, por meio de uma técnica
utilizando hipergrafos $r$-uniformes auxiliares. Assim, determinou-se
que a função limiar para a propriedade $tc_3(G(n,p)) \leq 3$ é $p =
\left(\frac{\log n}{n}\right)^{1/4}$. Neste trabalho, apresentamos os
avanços realizados ao longo do tempo, a respeito desse problema, bem
como apresentamos de forma detalhada várias técnicas relevantes em
Combinatória, as quais foram utilizadas para a obtenção desses
avanços.


MEMBROS DA BANCA:
Presidente - Interno ao Programa - 663.207.043-49 - GUILHERME OLIVEIRA MOTA - USP
Membro Titular - Examinador(a) Externo à Instituição - FÁBIO HAPP BOTLER - UFRJ
Membro Titular - Examinador(a) Externo à Instituição - JOSÉ DIEGO ALVARADO MORALES - USP
Membro Suplente - Examinador(a) Externo à Instituição - ROBERTO FREITAS PARENTE - UFBA
Notícia cadastrada em: 23/08/2022 14:14
SIGAA | UFABC - Núcleo de Tecnologia da Informação - ||||| | Copyright © 2006-2022 - UFRN - sigaa-2.ufabc.int.br.sigaa-2-prod