Quasimetric spaces : diameter versus numbers of lines

Abstract

El teorema clásico de De Bruijn y Erdös establece que cualquier conjunto de n puntos en el plano euclidiano, que no se encuentren todos sobre una misma línea, determina al menos n líneas distintas. Este resultado fundamental de la geometría combinatoria inspiró a Chen y Chvátal a proponer una conjetura que extiende esta idea a espacios métricos finitos: todo espacio de este tipo debe contener una línea universal o tener al menos tantas líneas como puntos. Aunque la conjetura ha sido confirmada para varias clases de espacios, su resolución completa sigue abierta.

En este contexto, la presente tesis explora el comportamiento de las líneas en espacios cuasimétricos finitos. Buscamos descripciones estructurales de grafos, dígrafos y espacios cuasimétricos, identificando configuraciones precisas que minimizan el número de líneas, especialmente bajo restricciones sobre el diámetro.

Nuestros resultados destacan la interacción entre diámetro, pocas líneas y estructuras de betweenness, y revelan diferencias clave entre los marcos métricos y cuasimétricos. En conjunto, este trabajo contribuye al desarrollo de la teoría combinatoria de líneas en espacios finitos y ofrece nuevas perspectivas para comprender las propiedades que subyacen a la Conjetura de Chen–Chvátal.

The classical theorem of De Bruijn and Erdös states that any set of n points in the Euclidean plane, not all lying on a single line, determines at least n distinct lines. This fundamental result in combinatorial geometry inspired Chen and Chvátal to propose a conjecture extending this idea to finite metric spaces: every such space should either possess a universal line or have at least as many lines as points. Although the conjecture has been confirmed for several classes of spaces, its full resolution remains open. In this context, the present thesis explores the behavior of lines in finite quasimetric spaces. We seek for structural descriptions of graphs, digraphs, and quasimetric spaces, identifying precise configurations that minimize the number of lines, specially when a restriction on the diameter is considered. Our results highlight the interplay between diameter, few lines, and betweenness structures, and reveal key distinctions between metric and quasimetric frameworks. Altogether, this work advances the combinatorial theory of lines in finite spaces and offers new perspectives for understanding the properties underlying the Chen–Chvátal Conjecture.