En matemáticas, particularmente en teoría geométrica de grafos, un grafo de distancias unitarias es aquel formado a partir de una colección de puntos en el plano, de manera que la distancia entre dos puntos directamente conectados entre sí sea siempre exactamente uno. Para distinguir estos grafos de una definición más amplia que permite que algunos pares de vértices no adyacentes estén a distancia uno, también se les puede llamar grafos de distancia unitaria estricta o grafos de distancia unitaria fiel. Como familia hereditaria de grafos, se pueden caracterizar mediante subgrafos inducidos prohibidos. Los grafos de distancia unitaria incluyen el grafo cactus, los grafos de cerillas y los grafos de peniques, así como el grafo hipercubo. Los grafos de Petersen generalizados son grafos de distancia unitaria no estricta.

Un problema planteado por Paul Erdős, conocido como el problema de la distancia unitaria, pide hallar el número máximo posible de pares de distancia unitaria determinados por puntos en el plano euclídeo. De forma equivalente, solicita el número máximo de aristas en un grafo de distancia unitaria con vértices. El mejor límite superior conocido es . El mejor límite inferior conocido es (para suficientemente grande). El número de colores necesarios para colorear T grafos de distancia unitaria también es desconocido. En el problema de Hadwiger-Nelson equivalente para el plano, algunos grafos de distancia unitaria requieren cinco colores, y cada grafo de distancia unitaria puede colorearse con siete colores. Para cada número algebraico existe un grafo de distancia unitaria con dos vértices que deben estar a una distancia Según el teorema de Beckman-Quarles, las únicas transformaciones del plano que preservan todos los grafos de distancia unitaria son isometrías.

Es posible construir un grafo de distancia unitaria de manera eficiente, dados sus puntos. Encontrar todas las distancias unitarias tiene aplicaciones en búsqueda de patrones, donde puede ser un primer paso para encontrar copias congruentes de patrones más grandes. Sin embargo, determinar si un grafo dado puede representarse como un grafo de distancia unitaria es NP difícil, y más específicamente completo para la teoría existencial de los números reales.

Definición

El grafo de distancia unitaria para un conjunto de puntos en el plano es aquel grafo que tiene esos puntos como sus vértices, con una arista entre dos vértices siempre que su distancia euclídea sea exactamente uno. Se dice que un grafo abstracto es un grafo de distancia unitaria si es posible encontrar ubicaciones distintas en el plano para sus vértices, de modo que sus aristas tengan longitud unitaria y de modo que todos los pares de vértices no adyacentes tengan distancias no unitarias. Cuando esto es posible, el grafo abstracto es isomorfo al grafo de distancia unitaria de las ubicaciones elegidas. Alternativamente, algunas fuentes utilizan una definición más amplia, permitiendo que pares de vértices no adyacentes estén a distancia unitaria. Los grafos resultantes son los subgrafos de los grafos de distancia unitaria (como se definen aquí). Cuando la terminología puede ser ambigua, los grafos en los que las no aristas deben estar a una distancia no unitaria pueden llamarse grafos de distancia unitaria estricta o grafos de distancia unitaria fieles. Los subgrafos de los grafos de distancia unitaria son equivalentes a los grafos que se pueden dibujar en el plano usando solo una longitud de arista. Para abreviar, este artículo se refiere a estos como "grafos de distancia unitaria no estrictos".

Los grafos de distancia unitaria no deben confundirse con los grafos de disco unidad, que conectan pares de puntos cuando su distancia es menor o igual a uno, y se utilizan frecuentemente para modelar redes de comunicación inalámbricas.

Ejemplos El grafo completo con dos vértices es un grafo de distancia unitaria, al igual que el grafo completo con tres vértices (el grafo triángulo), pero no el grafo completo con cuatro vértices. Generalizando el grafo triangular, todo grafo ciclo es un grafo de distancia unitaria, representado por un polígono regular. Dos grafos finitos de distancia unitaria, conectados por un único vértice común, generan otro grafo de distancia unitaria, ya que uno puede rotarse con respecto al otro para evitar distancias unitarias adicionales no deseadas. Al conectar grafos de esta manera, todo árbol o grafo cactus finito puede representarse como un grafo de distancia unitaria.

Cualquier producto cartesiano de grafos de distancia unitaria produce otro grafo de distancia unitaria, aunque esto no se cumple para otros productos de grafos comunes. Por ejemplo, el producto fuerte de grafos, aplicado a dos grafos no vacíos cualesquiera, produce subgrafos completos con cuatro vértices, que no son grafos de distancia unitaria. Los productos cartesianos de grafos camino forman un gráfico de celosía de cualquier dimensión. Los productos cartesianos del grafo completo de dos vértices son el grafo hipercubo, y los productos cartesianos de grafos triangulares son el grafo de Hamming, .

Otros grafos específicos que son grafos de distancia unitaria incluyen: el grafo de Petersen,; el grafo de Heawood, el grafo rueda, y (el único grafo rueda que es un grafo de distancia unitaria), así como el huso de Moser y el grafo de Golomb (pequeños grafos de distancia unitaria 4-cromáticos). Todos los grafos de Petersen generalizados, como el grafo de Möbius-Kantor que se muestra en la imagen, son grafos de distancia unitaria no estrictos.

Los grafos de cerillas son un caso especial de grafos de distancia unitaria, en los que no hay aristas que se crucen. Cada grafo de fósforos es un grafo plano, pero algunos grafos de distancia unitaria que de otro modo serían planos (como el huso de Moser) tienen un cruce en cada representación como grafo de distancia unitaria. Además, en el contexto de los grafos de distancia unitaria, el término plano debe usarse con precaución, ya que algunos autores lo utilizan para referirse al plano en el que se definen las distancias unitarias, en lugar de a una prohibición de cruces. Los grafos de peniques son un caso aún más especial de grafos de distancia unitaria y de cerillas, en los que cada par de vértices no adyacentes está separado por más de una unidad.

Propiedades Número de aristas

planteó el problema de estimar cuántos pares de puntos en un conjunto de puntos podrían estar a distancia unitaria entre sí. En términos de teoría de grafos, la pregunta plantea cuán denso puede ser un grafo de distancia unitaria, y la publicación de Erdős sobre esta cuestión fue uno de los primeros trabajos en teoría de grafos extremales.

Sea este número Una construcción con los grafos de hipercubo y los grafos de Hamming muestra que Al considerar puntos en una cuadrícula cuadrada con espaciado cuidadosamente elegido, Erdős encontró el límite inferior mejorado para alguna constante El artículo también estableció el límite superior

Debido a que el límite superior es mientras que el límite inferior está dominado por cualquier para cualquier constante Erdős conjeturó que, para cualquier Para una prueba o refutación de la conjetura ofreció un premio de 300 dólares, que posteriormente aumentó a 500 dólares. En mayo de 2026, esta conjetura fue refutada por un modelo de IA procesado por OpenAI, mediante una construcción para la que , donde . La construcción utiliza la teoría de números algebraicos, específicamente el método de torre de campo de clase. La cota se mejoró rápidamente a por Will Sawin. Este es un ejemplo de las diversas conexiones de los grafos de distancia con cuestiones relacionadas con números algebraicos y la rigidez. Como corolario, esto refuta una conjetura de Erdős y Fishburn (Erdős ofreció 500 dólares por una prueba, pero solo 50 dólares por una refutación).

En la otra dirección, la mejor cota superior conocida para este problema es: Esta cota puede interpretarse como un conteo de incidencias entre puntos y círculos unitarios, y está estrechamente relacionada con la desigualdad del número de cruces y con el teorema de Szemerédi-Trotter sobre incidencias entre puntos y líneas.; ; ;

En 1959, Erdős y Leo Moser plantearon el caso especial de este problema para los vértices de un polígono convexo. En este caso, el número máximo de distancias unitarias es como máximo . Solo se conoce una cota inferior lineal, .

Para valores pequeños de , se conoce el número máximo exacto de aristas posibles. Para , estos números de aristas son:

.

El problema se puede generalizar a las normas euclídeas en . Para con par, Erdos demostró que Para con impar, Erdos y Pach demostraron que El caso de está abierto. Los mejores resultados son para el límite inferior y para el límite superior, para cualquier

El problema puede generalizarse a normas arbitrarias en Dada una norma se define en consecuencia. El problema se resuelve en el caso genérico. Específicamente, dado cualquier entero para casi todas las normas

.

Es decir, el conjunto de normas que violan esta condición es exiguo en el conjunto de todas las normas de consideradas como espacio métrico, metrizadas por la distancia de Hausdorff entre las bolas de la unidad de norma. En este sentido, la norma euclídea sobre es especial, ya que se encuentra dentro de este conjunto reducido.

Por otro lado, construyó una métrica sobre similar a la euclídea, pero con lo que sugiere que, para la pregunta original, mejorar implicará el uso de alguna propiedad sutil de la norma euclídea en particular.

Subgrafos prohibidos Si un grafo dado no es un grafo de distancia unitaria no estricta, tampoco lo es ningún supergrafo de . Una idea similar funciona para grafos de distancia unitaria estricta, pero usando el concepto de subgrafo inducido, un subgrafo formado por todas las aristas entre pares de vértices en un subconjunto dado de vértices. Si no es un grafo de distancia unitaria estricta, entonces tampoco lo es ningún otro que tenga a como subgrafo inducido. Debido a estas relaciones, si un subgrafo o su supergrafo es un grafo de distancia unitaria, es posible describir los grafos de distancia unitaria mediante sus subgrafos prohibidos. Estos son los grafos mínimos que no son grafos de distancia unitaria del tipo dado. Se pueden usar para determinar si un grafo dado es un grafo de distancia unitaria, de cualquier tipo. es un grafo de distancia unitaria no estricta, si y solo si no es un supergrafo de un grafo prohibido para los grafos de distancia unitaria no estricta. es un grafo de distancia unitaria estricta, si y solo si no es un supergrafo inducido de un grafo prohibido para los grafos de distancia unitaria estricta.

Para los grafos de distancia unitaria estricta y no estricta, los grafos prohibidos incluyen tanto el grafo completo como el grafo bipartito completo . Para , dondequiera que se coloquen los vértices en el lado de dos vértices de este grafo, hay como máximo dos posiciones a distancia unitaria de ellos para colocar los otros tres vértices, por lo que es imposible colocar los tres vértices en puntos distintos. Estos son los únicos dos grafos prohibidos para los grafos de distancia unitaria no estricta en hasta cinco vértices. Hay seis grafos prohibidos en hasta siete vértices y 74 en grafos de hasta nueve vértices. Debido a que pegar dos grafos de distancia unitaria (o subgrafos de los mismos) en un vértice produce grafos de distancia unitaria estricta (respectivamente no estricta), cada grafo prohibido es un grafo biconectado, uno que no puede formarse mediante este proceso de pegado.