Banca de DEFESA: JULIANE KRISTINE DE LIMA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
STUDENT : JULIANE KRISTINE DE LIMA
DATE: 14/09/2022
TIME: 15:00
LOCAL: https://meet.google.com/zox-cazs-izq
TITLE:

Covering random graphs by monochromatic components

PAGES: 20
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUBÁREA: Teoria da Computação
SPECIALTY: Análise de Algoritmos e Complexidade de Computação
SUMMARY:

Many problems concerning vertex partitioning and covering in graphs
are still open, even though they have been present in the
literature for more than 50 years. In this work, we are interested
in determining the smallest number $t$ of monochromatic components
needed to cover all the vertices of a binomial random graph,
considering any edge coloring with $r=3$ colors, a property we
denote by $tc_r(G(n,p) )) \leq t$. In the case of $G(n,p)$, in
which the edge density varies as a function of $p=p(n)$, the aim of
this research was to investigate the value of $p$ which
characterizes a threshold function for the property $tc_3 (G(n,p))
\leq 3$. Bal and De Biasio proposed this problem in 2017 and, since
then, some papers have brought advances in understanding this
property. By constructing a counterexample, Ebsen, Mota and
Schnitzer determined a lower bound for $tc_r(G(n,p)) \leq t$, which
occurs asymptotically almost surely with $p \ll \left(\frac {\log
n}{n}\right)^{1/4}$. In 2021, Brada\v{c} and Buci\'{c}
determined the upper bound for the same property with the value of
$p \gg \left(\frac{\log n}{n}\right)^{1 /4}$, through a technique
using auxiliary $r$-uniform hypergraphs. Thus, the threshold
function for the property $tc_3(G(n,p)) \leq 3$ was determined with
the value $p = \left(\frac{\log n}{n}\right)^{1/ 4}$. In this work,
we present the advances made over time regarding this problem, as
well as we present in detail several relevant techniques in
Combinatorics, which were used in order to obtain these advances.

BANKING MEMBERS:
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