Two Problems In Combinatorics: Roller Coaster Permutations & The Erdös-Sós Conjecture
Autores
|
7134 |
3140,3049
|
|
|
7135 |
3140,3049
|
Informações:
Publicações do PESC
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.
Combinatorics is, as its name suggests, the science of combinations. Throughout this work, we focus on two main sub-areas of Combinatorics: Permutations and Graphs. Albeit two very related fields, we deal with them in a separate matter.
In Permutations, we study the problem of the Roller Coaster permutations, which are permutations that maximize, along with its subsequences, the number of ascents and descents. This special class of permutations was introduced in 2013 by T. Ahmed and H. Snevily which, besides its definition, conjectured many properties on its structure. In this work, we present an alternative and equivalent definition for the Roller Coaster permutations, together with an Integer Linear Programming model to find such permutaions. With this model, we obtained new examples for Roller Coasters, and, with an extended version of this model, based on certain structural conjectures, we obtained new candidates for Roller Coasters. Lastly, we motivated the study of this problem from another point of view, presenting conjectures related to other representations of permutations.
In Graphs, we present an extensive collection of results with respect to the famous Erd?s-Sós Conjecture, which are found in the literature. In 1962, P. Erd?s and V. Sós conjectured that for positive integers n, k, every graph on n vertices and at least n(k ? 2)/2 + 1 edges, contains every tree on k vertices. In this work, we divided the partial results in four main directions, each representing a different weakening of this conjecture, with the objective of pointing out possible directions to contribute to the state of the art with respect to this problem.