Banca de QUALIFICAÇÃO: PAULO MATIAS DA SILVA JUNIOR

Uma banca de QUALIFICAÇÃO de DOUTORADO foi cadastrada pelo programa.
DISCENTE : PAULO MATIAS DA SILVA JUNIOR
DATA : 15/07/2022
HORA: 14:00
LOCAL: por participação remota
TÍTULO:

RAMSEY AND ANTI-RAMSEY TYPE PROBLEMS IN DETERMINISTIC AND RANDOM GRAPHS

PÁGINAS: 38
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:

This is the doctoral qualification text and focuses on the study of
Ramsey, size-Ramsey and anti-Ramsey properties of random and
deterministic graphs. First, we consider the problem proposed by
Conlon and Tyomkyn, of determining the smallest number of colors
necessary to properly color the edges of the complete graph K_n, so
that no pair of vertex-disjoint triangles of K_n have the same triple
of colors. This amount of colors was unknown for even n and we were
able to compute it for some small cases and also for an infinite
family of values of n. We also consider the following anti-Ramsey
problem: given graphs G and H, we denote by G -> H the property in
which every proper coloring of E(G) presents a rainbow copy of H in
G. We determine the value of the threshold function for G(n, p) ->
K_{\ell,\ell}, for complete bipartite graphs K_{\ell,\ell}, with \ell
≥ 7. Finally, the size-Ramsey number of a graph H is the smallest
integer m for which there exists a graph G with m edges such that in
every 2-coloring of E(G), there is a monochromatic copy of H. In the
variant of the size-Ramsey number for oriented graphs, we verify that
invert the orientation of a single edge of an m-edges star makes this
parameter quadratic.

MEMBROS DA BANCA:
Presidente - Interno ao Programa - 663.207.043-49 - GUILHERME OLIVEIRA MOTA - USP
Membro Titular - Examinador(a) Externo à Instituição - CARLOS HOPPEN - UFRGS
Membro Titular - Examinador(a) Externo à Instituição - FABRICIO SIQUEIRA BENEVIDES - UFC
Membro Suplente - Examinador(a) Externo à Instituição - FÁBIO HAPP BOTLER - UFRJ