Dibujo de grafos planares con borde entero de longitudes de

Question

Es bien sabido que cada plano gráfico tiene una incrustación de tal forma que cada borde se dibuja un segmento de línea recta (Fáry del Teorema). Kemnitz y Harborth hizo la siguiente conjetura más fuerte

Conjetura 1. Cada plana gráfica tiene una recta de incrustación con entero borde de longitudes.

Me preguntaba si es posible atacar este problema con el siguiente enfoque.

Conjetura 2. Deje $X:=\{ x_1, \dots, x_n \}$ ser un conjunto finito de puntos en el plano tales que no hay tres puntos de $X$ son colinear. Para cualquier $\epsilon >0$ existe $X':=\{x_1', \dots, x_n'\}$ tal que para todos los $i, j \in [n]$

1. $d(x_i, x_i') < \epsilon$,
2. $d(x_i', x_j') \in \mathbb{Q}$, y
3. no hay tres puntos de $X'$ son colinear.

Para demostrar la Conjetura 2, es suficiente para demostrar la siguiente conjetura.

Conjetura 3. Deje $X:=\{ x_1, \dots, x_n \}$ ser un conjunto finito de puntos en el plano tales que no hay tres puntos de $X$ son colinear y todos los pares distancias son racionales. Entonces el conjunto de puntos que están a la distancia racional de todos los puntos en $X$ es un subconjunto denso del plano.

Conjetura 3 es trivial para $n=1$ y fácil para $n=2$. Almering comprobó $n=3$, y creo que está abierto para $n>3$. Tenga en cuenta que la Conjetura 3 es (esencialmente) un debilitamiento de:

Conjetura 4. Existe un subconjunto denso del plano con todos los pares distancias racional.

Esta pregunta fue planteada por Ulam en 1945 (ver este mathoverflow pregunta para obtener más información). Así, la razón por la que me gusta Conjetura 3 es que es todavía lo suficientemente fuerte como para demostrar la Conjetura 1, pero parece mucho más débil que la Conjetura de 4. Por desgracia, la Conjetura 3 está más allá de mi zona limitada de la experiencia. Por lo tanto:

Pregunta. ¿Cuáles son las perspectivas para demostrar la Conjetura de 3? Una prueba o refutación sería fantástico. Sin embargo, incluso con argumentos lo que sugiere que es de verdadero/falso, pero dicen que más allá de la tecnología actual sería la mayoría de la recepción.

Answer 1

No se muy bien la respuesta, pero:

1. El Kemnitz/Harborth conjetura fue demostrado para cúbicos grafos planares en:

Línea recta incrustaciones cúbicos grafos planares con borde entero de longitudes de Jim Geelen1, Anjie Guo2,†, David McKinnon3 (Diario de la Teoría de grafos, 2008)

Que el estado de una condición que implicaría Kemnitz/Harborth (propiedad 3.1 en su papel).

Ellos citan el siguiente teorema, que se relaciona con, pero no es el mismo, lo que conjetura:

Teorema 2.1 (Berry 1992, Acta Arith). Si $A, B, C \in \mathbb{R}^2$ no son puntos colineales tal que $dist(A, B), dist(A, C)^2,$ e $dist(B, C)^2$ son racionales, entonces el conjunto de puntos que están a una distancia racional de cada una de las $A, B, C$ forma un subconjunto denso de $\mathbb{R}^2.$

Answer 2

Creo que la conjetura de 3 en realidad es más resistente que la conjetura de 4.

Demuestro $C_3\implies C_4$:

Elija cualquier secuencia de enteros $a_n$, que contiene todos los enteros infinitas veces.

Elija cualquier enumeración de todas las plazas $s_n$ en el avión con esquinas racional de coordenadas.

A continuación, suponiendo que la conjetura 3, en el paso $n$ podemos encontrar un punto racional distancias en $s_{a_n}$ que no es colineal a cualquier utilizados previamente racionales, ya que hay sólo un número finito de líneas rectas en nuestra serie hasta el momento.

En el paso $\omega$, tenemos $\omega$ muchos racionales en cada plaza, por lo que un denso conjunto de todos racional distancias.

Answer 3

Problema D19 en las páginas 283-287 de Chico, Problemas sin resolver En la Teoría de números, se pregunta, "¿hay un punto cuyas distancias desde las esquinas de la unidad cuadrados son racionales?" Esto sugiere que incluso una débil forma de Conjetura 3 está abierta (o, a partir de 2004).