Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / En 1995 Komlós, Sárközy y Szemerédi probaron que para cualquier $\delta>0$ y cualquier entero positivo $\Delta$, todo grafo $G$ de orden $n$, con $n$ suficientemente grande, que satisfaga $\delta(G)\geq (1+\delta)\frac{n}{2}$, contiene como subgrafo a todo árbol de $n$ vértices y grado máximo acotado por $\Delta$. En esta memoria se presentan dos posibles generalizaciones de este resultado, estableciendo condiciones suficientes para el \textit{embedding} de árboles de orden $k$ en grafos con grado mínimo al menos $(1+\delta)\frac{k}{2}$, donde $k$ es lineal en el orden del grafo anfitrión. En 1963 Erd\H{o}s y Sós conjeturaron que, dado un entero $k$, un grafo $G$ con grado promedio mayor que $k-1$ debería contener todos los árboles en $k$ aristas como subgrafos. Como consecuencia de uno de los resultados principales de esta memoria, se demuestra una versión parcial de la conjetura de Erd\H{o}s-Sós. Siguiendo la linea del \textit{embedding} de árboles en grafos con condiciones de grado mínimo, Havet, Reed, Stein y Wood conjeturaron el 2016 que todo grafo con grado mínimo al menos $\lfloor\frac{2k}{3}\rfloor$ y grado máximo al menos $k$ contiene todo árbol con $k$ aristas como subgrafo. Las técnicas aquí desarrolladas permiten, adicionalmente, probar una versión parcial de esta conjetura. / CMM - Conicyt PIA AFB170001

Ingeniero Civil en Computación / Chile es el país mas largo del mundo con sobre 4300 km de longitud y un ancho promedio de 180 km. Armar una red que abastezca de internet al país naturalmente tiende a unir del extremo norte al extremo sur. Esta tendencia suele comprometer la robustez de la red, haciendo que fallas en esta se propaguen dejando incomunicado al país. En el marco de los proyectos InnovaChile CORFO se propone llevar a cabo el proyecto Estudio y Recomendaciones sobre la Resiliencia de la Infraestructura del Internet Chileno .En este proyecto se realizará un mapa que represente como un grafo la infraestructura de lared a nivel país, para luego hacer estudios acerca de la robustez de ésta. El objetivo es entonces resolver el problema de la creación y mantención de un grafo que represente la red física del internet chileno. Para llevar a cabo el objetivo de la memoria se realiza un análisis del estado previo de la labor de crear y mantener la red, para luego describir casos de uso y definir condiciones para completar el desarrollo. Se hace un estudio de tecnologías para apoyar la creación de la solución y se procede con ella. Se agregan features para creación y modificación del grafo, incluyendo un sistema de historial de acciones para hacer time travel sobre este. Se hace pruebas con datos ficticios para luego usar los datos reales previamente recolectados manualmente. Se valida la solución en términos de cumplirse los casos de uso definidos, usabilidad de la solución y cumplimiento de objetivos específicos. El resultado final es una aplicación web que permite la creación y mantención colaborativa de la red de internet chileno. / Este trabajo ha sido financiado por NIC Labs, CORFO

Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / El k-coloreo de vértices de un grafo es un ya conocido problema NP-completo, debido a esto, los esfuerzos se han concentrado en estudiar el problema restringido a ciertas clases de grafos, para intentar resolverlo en tiempo polinomial. Dentro de las clases de grafos más estudiada, están los grafos H-free, que son los grafos que no poseen un grafo isomorfo a H como subgrafo inducido. En el presente trabajo se investigó el problema de 3-coloreo en las clases de grafos (P_{2d+3},C_{≤ 2d-1})-free (donde C_{≤2d−1} = {C_{2k+1} ∣ k ∈ N y k ≤ d}), para d ≥ 3, obteniendo los siguientes resultados: Para el caso particular d = 3, se puede decidir si un grafo G de la clase ( P_9, C_5, C_3)-free posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4). Para todo d ≥ 3, se puede decidir si un grafo G de la clase (P_{2d+3},C_{≤ 2d-1}, C_8)-free posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4). Para todo d ≥ 3, se puede decidir si un grafo G de la clase ( P_{2d+3}, C_{≤2d−1})-free, que tiene un ciclo C de largo 2d + 3 como subgrafo inducido, posee un 3-coloreo (y encontrarlo si es que existe) en tiempo O(∣V (G)∣^4). / CMM - Conicyt PIA AFB170001

Magíster en Ciencias, Mención Computación. Ingeniero Civil en Computación / La dependencia de la gente, las empresas y el gobierno con los sistemas de telecomunicaciones se ha vuelto muy fuerte y vital en la mayoría de los casos. Una falla en estos sistemas, como por ejemplo Internet, puede ocasionar pérdidas en muchos sentidos paralizando casi cualquier tipo de industria. Así, estudiar estas fallas y fenómenos ha atraído a muchos investigadores a proponer modelos para detectarlas, estudiarlas y desarrollar acciones de mitigación y prevención. Uno de estos enfoques, es la medición de robustez de estos sistemas usando teoría de grafos, modelándolo abstractamente como elementos interconectados entre sí. El objetivo de este trabajo se enfoca en la evaluación y mejora de este sistema bajo la mirada de las redes complejas. Específicamente, sobre la robustez de la red física del Internet chileno, que dada la geografía del país es muy vulnerable tanto a desastres de factores naturales o humanos. Dado que el campo de las redes complejas es extremadamente extenso en la comunidad científica, es necesario estudiar los diversos sistemas y modelos propuestos, de tal manera a elegir aquel que más se adecúe a la problemática mencionada anteriormente. En detalle, se necesita una métrica adecuada para medir la robustez del sistema. Este trabajo consiste en un estudio exhaustivo de métricas de robustez para luego aplicarlas al contexto chileno. La metodología de este trabajo consiste en aplicar una técnica muy usada en el ámbito científico llamada estudio de mapeo sistemático. Esta revisión, bajo algunos antecendentes, responde la siguiente pregunta de investigación, qué métricas existen para estudiar la robustez en redes complejas, realizando una búsqueda en diversos repositorios académicos. Los resultados de este trabajo indican que la mayoría de la comunidad científica se ha concentrado en problemas de mayor escala, que no están sujetas a la particular geografía del territorio chileno. Otra razón por la cual aquellas métricas no son útiles para nuestro caso es que la mayoría darían resultados poco favorables dado que la red es intrínsecamente poco robusta. Las mejoras propuestas indican correlaciones favorables sobre una métrica en particular, sobre una topología similar a menor escala, el impacto nodal de Wiener (no presente dentro de los resultados del mapeo sistemático), que aparte de poseer una buena conectividad como requisito, toma en cuenta tanto las distancias (latencias) de la red, como la calidad de sus caminos alternativos (en caso de falla). Finalmente, como trabajo futuro principal se aplicarán estas mejoras a la red real, tomando en cuenta las distancias geográficas y sus costes asociados, así como la evaluación correspondiente por la métrica elegida. / Este trabajo ha sido parcialmente financiado por NIC CHILE RESEARCH LABS

Tesis para optar al grado de Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / The main focus of this thesis is the study of monochromatic cycle partitions in uniform hypergraphs. The first part deals with Berge-cycles. Extending a result of Rado to hypergraphs, we prove that for all $r,k \in \N$ with $k \geq 2$, the vertices of every $r(k-1)$-edge-coloured countably infinite complete $k$-uniform hypergraph can be core-partitioned into at most $r$ monochromatic Berge-cycles of different colours. We further describe a construction showing that this result is best possible. The second part deals with $\ell$-cycles. We show that for all $\ell, k, n \in \N$ with $\ell \leq k/2$ the following hypergraph-variant of Lehel's conjecture is true. Every $2$-edge-colouring of the $k$-uniform complete graph on $n$ vertices has at most two disjoint monochromatic $\ell$-cycles in different colours that together cover all but a constant number of vertices, where the constant depends on $k$ and $\ell$. Furthermore, we can cover all vertices with at most $4$ ($3$ if $\ell \leq k/3$) disjoint monochromatic $\ell$-cycles. The third part deals with tight-cycles in $2$-edge-colourings of complete $3$-uniform hypergraphs. We show that for every $\eta > 0$ there exists an integer $n_0$ such that every $2$-edge-colouring of the $3$-uniform complete hypergraph on $n \geq n_0$ vertices contains two disjoint monochromatic tight cycles of distinct colours that together cover all but at most $\eta n$ vertices. Finally, the fourth part deals with tight-cycles in a more general setting. We prove that for every $k,r \in \N$, the vertices of every $r$-edge-coloured complete $k$-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles, confirming a conjecture of Gy\'arf\'as. We further prove that for every $r,p \in \N$, the vertices of every $r$-edge-coloured complete graph can be partitioned into a bounded number of $p$-th powers of cycles, settling a problem of Elekes, D. Soukup, L. Soukup and Szentmikl\'ossy. In fact we prove a common generalisation of both theorems which further extends these results to all host hypergraphs with bounded independence number. / CONICYT/Doctorado Nacional/2014-21141116, CMM-Conicyt PIA AFB170001

Ingeniero Civil en Computación / A partir de información representada en una colección de declaraciones en RDF (Resource Description Framework), esta representa intrínsecamente un multi-grafo etiquetado, dirigido. Con esto es posible utilizar algoritmos de búsqueda de caminos, que permiten encontrar la ruta más corta entre dos nodos. Con el fin de estudiar tecnologías basadas en el desarrollo de la web semántica, el tema de memoria propuesto consiste en la búsqueda de caminos relevantes para grafos en RDF. Para esto se construye una herramienta la que, a partir de un archivo con información en RDF, sea capaz de resolver consultas sobre caminos entre un nodo de origen y un nodo objetivo de tal manera que estos contengan información relevante para el usuario. La relevancia de los caminos se representa a través del peso asignado tanto a aristas, según su etiqueta, como a vértices, principalmente por métodos basados en su grado, PageRank o variaciones de estos. Para la búsqueda del camino mínimo entre un nodo origen y un nodo objetivo se implementa una versión del algoritmo de Dijkstra para grafos ponderados. Con el objetivo de tener la posibilidad de visualizar los resultados obtenidos y usar la herramienta en un contexto real para reportar resultados, es que se construye una aplicación que resuelva consultas de caminos entre dos nodos y represente esta respuesta gráficamente. Finalmente se realizan pruebas de rendimiento del algoritmo utilizado y pruebas para comparar los caminos resultantes de los distintos métodos de ponderación del grafo. Además se lleva a cabo una evaluación con usuarios para la validación de la solución obtenida.

Thesis (Ph. D.)--Royal Institute of Technology, Stockholm, 2005.