Banca de DEFESA: PAULO MATIAS DA SILVA JUNIOR
Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.STUDENT : PAULO MATIAS DA SILVA JUNIOR
DATE: 01/02/2024
TIME: 10:00
LOCAL: https://meet.google.com/tbp-zbeh-kbh
TITLE:
Edge coloring patterns and anti-Ramsey properties
PAGES: 55
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:
This text focuses on the study of 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 obtain a proper edge coloring of the complete graph Kn, so that no pair of vertex-disjoint triangles of Kn have the same triple of colors. This number of colors was unknown for n even and we were able to compute it for some small cases and also for an infinite family of n values. We also consider the following anti-Ramsey problem: given graphs G and H, we denote by G rb −→ H the property in which every proper coloring of E(G) contains a rainbow copy of H in G. We prove that the value of the threshold function for G(n, p) rb −→ Kℓ,r is given by n (ℓ+r−2)/(ℓr−1) , for complete bipartite graphs Kℓ,r with ℓ, r ≥ 3. We also prove that the threshold is asymptotically smaller than this value if ℓ = 2 and r ≥ 2.
COMMITTEE 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 - WALNER MENDONCA DOS SANTOS - USP
Membro Titular - Examinador(a) Externo à Instituição - LUIZ FREIRE MOREIRA - UFPE
Membro Titular - Examinador(a) Externo à Instituição - ROBERTO FREITAS PARENTE - UFBA
Membro Suplente - Examinador(a) Interno ao Programa - 3145512 - MAYCON SAMBINELLI
Membro Suplente - Examinador(a) Externo à Instituição - JOSÉ DIEGO ALVARADO MORALES - USP
Membro Suplente - Examinador(a) Externo à Instituição - TAISA MARTINS - UFF