Anti-thickness geométrico de gráficas completas con hasta diez vértices.

Anti-thickness geométrico de gráficas completas con hasta diez vértices

David Gustavo Merinos Sosa
 

Texto completo de la Tesis     

 


Resumen

La geometría combinatoria es el área de las matemáticas discretas y de la computación que estudian las propiedades combinatorias de objetos geométricos con características discretas (puntos, planos, rectas o gráficas geo-métricas). Está envuelta en problemas de coloración, simetría, partición y descomposición de dichos objetos geométricos. En esta tesis trabajamos un problema del área de la geometría combinatoria, particularmente con los objetos geométricos llamados gráficas geométricas de las cuales nos interesa estudiar un parámetro conocido como anti-thickness geométrico. Decimos que un dibujo o gráfica geométrica es un conjunto de puntos en el plano y un conjunto de rectas que conectan pares de puntos. Un thrackle es un subconjunto de dichas rectas, y sus extremos correspondientes, tales que cada par de rectas se cruzan o tienen un extremo en común, un thrackle es máximo cuando tiene el máximo número de rectas. Dada una gráfica, si encontramos el número mínimo de thrackles, para todos los dibujos de la gráfica, tales que cada arista pertenezca a exactamente un thrackle, habremos encontrado el anti-thickness geométrico de la gráfica dada. Encontrar el anti-thickness geométrico de una gráfica es un problema abierto en el área de la geometría combinatoria. Actualmente se conoce una cota inferior y la cota superior del anti-thickness geométrico para gráficas completas. La cota inferior se basa en contar cuántos thrackles son necesarios en un conjunto de tal manera que se cumplan las condiciones antes mencionadas y la cota superior se basa en encontrar un conjunto de thrackles, que cumplen con las condiciones establecidas para el problema, de un dibujo de la gráfica completa cuando sus puntos están en posición convexa. Una cuestión a tomar en cuenta con la cota inferior es que asume que cada par de thrackles máximos no tienen aristas en común, lo cual no es cierto en posición convexa. En el caso de la cota superior debe notarse que el dibujo con el que se dio ese resultado está en posición convexa y esto no nos dice mucho acerca del anti-thickness geométrico cuando el dibujo de la gráfica están en posición general no convexa.

En esta tesis encontramos el anti-thickness geométrico exacto para gráficas completas con hasta diez vértices. Usamos algoritmos computacionales para buscar thrackles en dibujos de gráficas completas y observamos que cada par de thrackles máximos se intersecta en al menos una arista lo que nos permitió probar que la cota inferior no es justa para gráficas con hasta diez vértices. Además hicimos observaciones con respecto a otras propiedades geométricas de los thrackles y las gráficas completas para encontrar una relación entre estas y el anti-thickness geométrico.

 

Abstract

Combinatorial geometry is the area of discrete mathematics and computer science which studies combinatoric properties of geometrical objects with discrete features (such as points, planes, lines or geometric graphs). It is envolved in coloring, symmetry, partition and decomposition problems of said geometrical objects. In this thesis we work on a combinatorial geometry problem, particularly with geometric graphs from which we wish to study a parameter currently known as geometric anti-thickness. We say a drawing or a geometric graph is a set of points in the plane and a set of straight lines connecting pairs of points, called edges. A thrackle is a subset of said edges and its corresponding extreme points such that each pair of edges in the subset either crosses or share an extreme point, a thrackle is maximum when it has the maximum number of edges. Given a graph, if we found the minimal number of thrackles, for every drawing of the graph, such that every edge belongs to exactly one thrackle, we would've found the geometric antithickness of the given graph. Finding the geometric anti-thickness is an open problem in combinatorial geometry. Currently, some lower and upper bounds are known. The lower bound is based on counting how many thrackles in a set are necessary such that the previous conditions hold. The upper bound was obtained by finding a set of thrackles with the previously mentioned conditions of a drawing of the complete graph when its points are in convex position. Note that in the lower bound it is assumed that every pair of maximal thrackles do not share an edge, this is not true for convex position. In the case of the upper bound, the result was achieved by using only one (convex) drawing and this does not give insight about geometric anti-thickness when the drawing is in non-convex general position.

In this thesis we find the exact geometric anti-thickness for complete graphs with up to ten vertices We use algorithms to find thrackles in complete graph drawings, we observed that every pair of maximal thrackles share at least one edge. This allowed us to proove that the lower bound is not tight for graphs with up to ten vertices. Besides, we made observations respecting other geometric properties of thrackles and complete graphs to find a relation between these and geometric anti-thickness