Longitudes distintas mínimas en gráficos completos
Ed Pegg
Normalmente, gráfico completo se dibuja como un regular -gon con todas las diagonales, o un -gon con un punto añadido en el centro. Ocasionalmente se utilizará una cuadrícula.
La mayor parte del tiempo, el -gon parece minimizar el número de longitudes de borde distintas. Pero no siempre. Por ejemplo, y necesita 6 y 9 longitudes distintas en cualquier forma poligonal. Las incrustaciones basadas en cuadrícula a continuación necesitan solo 5 y 8 longitudes distintas.
¿Existen otras soluciones que superen los métodos basados en cuadrículas y polígonos?
Respuestas (1)
alex ravski
De acuerdo con la solución del problema de distancias distintas de Erdős , el número mínimo de longitudes de borde distintas en un dibujo plano (línea recta) de es . La página de Wikipeadia contiene muchos enlaces relevantes, por lo que solo agrego dos enlaces a las preguntas de MathOverflow:
Conjuntos de puntos en el espacio euclidiano con un pequeño número de distancias distintas
Encontrar el número máximo de miembros en el club de matemáticas.
Número máximo de miembros en el club de matemáticas
Demuestre que el tamaño del gráfico de Turan Tr(n)Tr(n)T_r(n) es al menos (1−1r)(n2)(1−1r)(n2)(1 - \frac{1}{r} ) \binom{n}{2}.
Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2
Número mínimo de particiones de un conjunto dada lista de números que no pueden aparecer en la misma partición
Una pregunta sobre la expectativa del número cromático
Dibuja 7 líneas en el plano de manera arbitraria. Demuestre que para cualquier configuración de este tipo, 2 de esas 7 líneas forman un ángulo menor que 26◦
(Aclaración) Un gráfico con un número par de vértices tiene dos vértices con un número par de vecinos comunes
Una pregunta sobre un gráfico conexo con kkk
Número de caminos de longitud n+i en cuadrícula nxn con diagonal
Iván Neretín