Combinatória, como o nome sugere, é a ciência das combinações. Durante este trabalho, exploramos duas áreas principais da Combinatória: Permutações e Grafos. Embora muito próximas, tratamos as áreas de maneira separada.
Em Permutações, abordamos o problema das permutações Montanhas-Russas, que são permutações que maximizam, junto às suas subsequências, o quanto elas alternam entre subidas e descidas. Essa classe especial de permutações foi introduzida em 2013 por T. Ahmed e H. Snevily que, além de sua definição, levantaram diversas conjecturas sobre sua estrutura. Neste trabalho, apresentamos uma definição alternativa para essas permutações, bem como um modelo de Programa Linear Inteiro associado para encontrá-las. Através desse modelo, conseguimos obter novos exemplos de Montanhas-Russas, e, através de um modelo que adota restrições com base em certas conjecturas estruturais, obtivemos novas candidatas para Montanhas-Russas. Por fim, motivamos o estudo desse problema sob outras óticas, apresentando conjecturas relacionadas a outras representações de permutações.
Em Grafos, apresentamos uma vasta coleção de resultados a respeito da famosa Conjectura de Erd?s-Sós presentes na literatura. Em 1962, P. Erd?s e V. Sós conjecturaram que, para inteiros positivos n, k, todo grafo com n vértices e pelo menos n(k ? 2)/2 + 1 arestas contém, como subgrafo, todas as árvores com k vértices. Neste trabalho, dividimos tais resultados em quatro direções principais, cada uma representando um enfraquecimento diferente dessa conjectura, com o objetivo de apontar possíveis direções para contribuições ao estado da arte com respeito a esse problema.
.png)
.png)
