Aluno: Matheus Paulo Ferreira
Orientador: Guilherme Oliveira Mota
Considere bicolorações das arestas de um grafo G, ou seja, para cada aresta de G, vamos escolher uma cor entre azul e vermelho para colorí-la. Após esse processo, podemos dividir o grafo G em dois subgrafos geradores: um composto somente pelas arestas azuis, que chamaremos de G_blue e um composto somente pelas arestas vermelhas, que chamaremos de G_red.
Em especial, estamos interessados em saber quando que um desses dois subgrafos contém uma cópia de determinado grafo H. Assim, dado dois grafos G e H, dizemos que G → H se e somente se para toda bicoloração das arestas de G, ou G_blue ou G_red contém uma cópia de H.
Com isso, podemos definir para todo grafo H o seu número size-Ramsey r̂(H) como sendo:
r̂(H) = min(|E(G)| : G → H)
ou seja, o número size-Ramsey de um grafo é o número mínimo de arestas necessário para que um grafo G contenha uma cópia de H ou em G_blue ou em G_red para toda bicoloração possível.
Ao longo do tempo, diversos autores abordaram esse problema, sendo que para diversas classes simples de grafos, como caminhos, circuitos e estrelas, foi demonstrado que r̂(H) crescia de maneira linear com o número de vértices de H. Nesse contexto, J. Beck conjecturou que para todo grafo H de grau limitado, r̂(H) crescia de maneira linear com o número de vértices de H.
Essa conjectura motivou a busca por grafos de grau limitado com número size-Ramsey grande, ou seja, grafos H de grau limitado tal que r̂(H) cresça mais rápido que toda função linear em relação ao número de vértices de H. Essa revisão busca analisar dois artigos que buscaram esse tipo de grafo e discutir a estratégia utilizada para provar resultados como esses.