Cobertura de grafos aleatórios em componentes monocromáticas
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.