La conjetura de Erdös-Faber-Lovász (EFL) lleva mas de 40 años abierta, durante este tiempo ha sido de interés en varias áreas de la investigación científi ca como lo son la teoría de gráfi cas, la teoría de hipergráfi cas y la teora de diseños. Estudiamos una variante de la conjetura EFL, para gráficas geométricas. El caso particular que trabajamos se traduce al problema de encontrar el número máximo de triángulos sobre n puntos, que son disjuntos en aristas y se intersectan dos a dos, a estos conjuntos de triángulos les llamamos thrackles de triángulos.
Obtenemos el número máximo de triángulos que puede tener un thrackle de triángulos para valores pequeños de n de forma analítica, y utilizamos busquedas computacionales para valores de n más grandes. Entre los resultados que obtuvimos se encuentran cotas superiores tanto para el tamaño de un thrackle de triángulos, como para el número de thrackles distintos sobre un conjunto de puntos. A partir de estos resultados obtuvimos una cota de la complejidad computacional de hacer una búsqueda exhaustiva de todos los thrackles de triángulos. Los resultados que presentamos en esta tesis, dan evidencia de que el tamaño máximo de un thrackle de triángulos, es el conjeturado en el artículo que propuso el problema originalmente.
Abstract
The Erdös-Faber-Lovasz (EFL) conjecture has been open for more than 40 years. During this time the conjecture has been of interest in several areas of mathematics such as graph theory, hypergraph theory, and design theory. In this thesis we study a variant of the conjecture for geometric graphs. The speci c case we study can be translated to the problem of nding the maximum number of triangles over a set of n points, that are edge disjoint and intersect each other. We call this kind of triangle sets triangle thrackles.
We proof analytically the exact size of the maximum size of a triangle thrackle for small values of n, and use computational search to study how triangle thrackles behave for bigger values of n. We present bounds both for the size of a triangle thrackle, and for the number of distinct triangle thrackles over a point set. Based on these results, we obtain a lower bound on the computational complexity of doing an exhaustive search of triangle thrackles. The results presented in this thesis add evidence in support of a conjecture on the maximum size of a triangle thrackle, made in the publication that originally proposed the problem.
