Números de Ramsey multipartidos via estruturas discretas

Abstract

Resumo: Este trabalho aborda a versão multipartida dos números de Ramsey, com enfase na obtenção de classes exatas. Como ferramentas, utilizaremos Conceitos e resultados da teoria dos designs combinatórios bem como da teoria dos grafos. Em particular, computaremos o número de Ramsey multipartido para grafos estrela utilizando o índice cromático de certos grafos multipartidos completos, estendendo assim resultados de Burr e Roberts (1973), Chvátal e Harary (1972) e Irving (1974). Além disso, abordaremos o problema na versão multicolorida onde um dos grafos é ou um caminho, ou um ciclo, ou um emparelhamento e os demais grafos são todos estrelas. Neste caso, obtemos várias classes exatas, estendendo resultados de Parsons (1974), Cockayne e Lorimer (1975), Lawrence (1973) e Omidi, Raeisi e Rahimi (2018). Na literatura, vários números de Ramsey foram obtidos utilizando-se exatamente de uma classe de designs. Em contraste a isto, um dos principais resultados desta tese utiliza-se de duas classes de designs para obter uma classe exata dos números de Ramsey. Algo que parece ser sem precedentes na literatura e estende a construção de Exoo, Harborth e Mengersen (1991)

Abstract: This thesis deals with the multipartite version of Ramsey numbers, with an emphasis on obtaining exact classes. As tools, we will use concepts and results from combinatorial design theory as well as graph theory. In particular, we will compute the multipartite Ramsey number for star graphs using the chromatic index of certain complete multipartite graphs, thus extending results of Burr and Roberts (1973), Chvátal and Harary (1972) and Irving (1974). In addition, we will address the problem in the multicolored version where one of the graphs is either a path, or a cycle, or a matching and the other graphs are all stars. In this case, we obtain several exact classes, extending results of Parsons (1974), Cockayne and Lorimer (1975), Lawrence (1973) and Omidi, Raeisi and Rahimi (2018). In the literature, several Ramsey numbers were obtained using exactly one class of designs. In contrast to this, one of the main results of this thesis uses two classes of designs to obtain an exact class of Ramsey numbers. Something that seems to be unprecedented in the literature and extends the construction of Exoo, Harborth and Mengersen (1991).