Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Estudiamos una generalización del problema de la secretaria llamada el problema matroidal de la secretaria propuesta en 2007 por Babaioff et al. [1]. En este problema, los elementos de una matroide se revelan en orden aleatorio. Al observar un elemento, debemos decidir de forma irrevocable si incluirlo o no en nuestra solución. Los elementos aceptados deben formar un conjunto independiente y deseamos que sea cercano al independiente óptimo. En su trabajo, Babaioff et al. [1] conjeturaron la existencia de un algoritmo O(1)-competitivo para este problema en cualquier matroide. Dicha conjetura sigue abierta, y solo se ha podido probar en clases particulares de matroides. Por un lado esta tesis sirve como lectura introductoria al problema ya que incluye una introducción a lo que son las matroides y al problema de la secretaria. Por otro lado presentamos nuevos resultados sobre este problema. Desarrollamos una nueva técnica para diseñar y analizar algoritmos con la cual obtenemos nuevos algoritmos O(1)-competitivos para cuatro clases de matroides: transversales, gráficas, laminares y un tipo especial de matroides representables que llamaremos k-sparsas. En todos estos casos, nuestros algoritmos funcionan aún bajo hipótesis más restrictivas que las del problema original, y logran una mejor competitividad que la de los mejores algoritmos publicados para esos problemas. Además planteamos y estudiamos algunas variantes del problema. / Este trabajo ha sido parcialmente financiado por Fondecyt de Iniciación 11130266: APPROXIMATIONALGORITHMS FOR INCREMENTAL SELECTION PROBLEMS

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas, Programa de Pós-Graduação em Matemática Pura e Aplicada, Florianópolis, 2013 / Made available in DSpace on 2013-12-05T23:22:46Z (GMT). No. of bitstreams: 1 317580.pdf: 1015354 bytes, checksum: 52b9f27b4cc4ebcc38570dea415cea4c (MD5) / Neste trabalho serão descritas propriedades de ladrilhamentos nas mais diversas áreas da matemática como topologia, sistemas dinâmicos e topologia algébrica. Veremos um método para construir ladrilhamentos que não admitem simetrias de translação, isto é, não são periódicos. Tais ladrilhamentos são chamados de ladrihamentos de substituição e iremos construir um complexo celular associado e determinar sua cohomologia. O estudo será aplicado a alguns exemplos.<br> / Abstract : In this essay we show properties of tilings in many areas of mathematics like topology, dynamic systems and algebraic topology. We describe a method to build a tiling that doesn't admit a symmetry of translation, i.e., it is not periodic. Such tilings are called substitution tilings and we will construct an associated cell complex in order to determine its cohomology. The study will be applied to some examples.

En la presente memoria, se abordan cuatro problemas, existiendo en todos ellos una gran interacción entre la combinatoria y la geometría. El primer problema que se estudia es la introducción de varias extensiones del concepto de tipo de orden para nubes de puntos. Concretamente, se introducen los tipos de orden circulares y triángulares, en las versiones orientada y no orientada. Se han demostrado resultados combinatorios análogos a resultados bien conocidos sobre tipos de orden ordinarios, introducidos por Goodman y Pollack como es el llamado Teorema de ordenación geométrica. Se ha estudiado también la información geométrica que proporciona cada uno de estos conceptos. El segundo problema estudia el empaquetamiento plano de grafos; esto es, el trazado de grafos, disjuntos en aristas, en el plano. Hemos obtenido varios resultados sobre el empaquetamiento plano de árboles y ciclos. Concretamente, para árboles que no sean estrellas, se ha demostrado que siempre admiten empaquetamiento plano: dos copias de un árbol cualquiera, un árbol cualquiera y un camino, un árbol cualquiera y un ciclo. También se han obtenido resultados sobre empaquetamiento plano de dos o tres ciclos. La principal herramienta que se ha utilizado es la representación de un árbol en un polígono convexo con propiedades muy concretas. En tercer lugar se estudia el grafo T (P) de árboles geométricos de una nube de puntos P, siendo este grafo el que tiene por vértices los árboles generadores sin cortes de P y dos de tales árboles T1, T2 son aduacentes si y sólo s, T2C=t1e+f para ciertas aristas e y f. Se han obtenido propiedades combinatorias de estos grafos, especialmente en el caso particular en que el conjunto de puntos esta en posición convexa. En este caso se ha determinado el centro, radio y grupo de automofismos de estos grafos, y demostrado que son hamiltonianos y de conectividad máxima. Finalmente, también se ha estudiado el grafo Mm de los emparejamientos perfectos sin cortes de una nube de 2m puntos en posición convexa. Entre los resultados obtenidos cabe destacar que se ha demostrado que Mm es bipartito, hamiltoniano sólo si m es par y que el diámetro de Mm es igual a m-1, siendo todos los emparejamientos de excentricidad máxima.