RÁPIDA ACTUALIZACIÓN FINAL: Sólo quería darte las gracias MO usuarios por todo su apoyo. Un agradecimiento especial por la rapidez en las respuestas, he aceptado primera de ellas, se agradece la claridad que me dio. He actualizado mi toro algoritmo con ${\rm cr}(G)$. Funciona bien en mi sistema de prueba completo, es decir, la evidencia de ${\rm cr}(G)={\rm pcr}(G)$ sobre el toro. Más sobre esto más adelante, será una prueba más nítida enlazado desde la última respuesta así. Me voy a presentar en el tiempo! Gracias de nuevo MO usuarios por toda su ayuda!
Post Original:
Me disculpo si la "crisis" es una palabra demasiado fuerte, pero estoy en un modo de pánico, si esa es la palabra correcta: En dos semanas, yo debería ser la presentación de mi Tel. D. Tesis, pero acabo de recibir una mala noticia, o debería decir la información que me preocupa mucho. Es realmente una situación de emergencia:Mi tesis en ciencias de la computación, algoritmos relacionados con el gráfico de dibujos sobre la esfera y el toro. Uno de la piedra angular de los resultados matemáticos estoy confiando en que es el borde del gráfico cruce de lema (o borde de cruzar la desigualdad). Se da una cota inferior para el número mínimo de borde cruces ${\rm cr}(G)$ para cualquier dibujo de la gráfica de $G$ con $n$ vértices y $e$bordes $${\rm cr}(G)\geq \frac{e^3}{64n^2}$$ para $e>4n$.
PROBLEMA: estoy leyendo en el artículo de Pach y Tóth que hay una posibilidad de que las matemáticas papeles sobre el cruce de los números de operar con diferentes definiciones. No es el cruce de número de ${\rm cr}(G)$ (mínimo borde de cruces en un dibujo de $G$), pero también a la par de cruzar número ${\rm pcr}(G)$, el número mínimo de aristas que pares en el cruce de un dibujo de $G$. He comprobado mi algoritmos y, basándose en esta definición, claramente me aplique el par de cruzar número ${\rm pcr}(G)$
PREGUNTA CRÍTICA: ¿Puede confirmar que el borde de cruzar lema sigue siendo válido en la esfera y el toro también para el par de cruzar número ${\rm pcr}(G)$?
Referencia: János Pach y Géza Tóth. Que cruzar número es de todos modos? J. Combinat. La Teoría De La Ser. B, 80(2): 225-246, 2000.
Y el artículo de la Wikipedia como un punto de partida https://en.wikipedia.org/wiki/Crossing_number_inequality
Respuestas
¿Demasiados anuncios?$\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$Para el par de cruzar número $\pcr(G)$, la respuesta corta es sí el cruce lema tiene para los dibujos de la esfera, pero no se sabe si también se mantiene en el toro.
La mejor y más actual de referencia para usted podría ser la encuesta el artículo de Schaefer, actualizada en febrero de 2020: "La Gráfica de Cruzar Número y sus Variantes: Una Encuesta de la Revista Electrónica de la Combinatoria (https://doi.org/10.37236/2713).
Las páginas relevantes para usted son las páginas 5 y 6 con la siguiente cita de Schaefer:
"Desde el Hanani–Tutte es el teorema de no se sabe que es cierto para el toro, esto significa que en la actualidad no podemos tener una prueba de que el cruce lema para $\pcr$ o $\pcr_−$ sobre el toro."
Generalmente, $\pcr(G)\leq \cr(G)$. Es todavía un problema abierto si son iguales o no. Las primeras pruebas de la travesía lema no hacer la distinción. El primero en levantar la ambigüedad se Mohar (1995) en un discurso de la conferencia.
El Pach y Tóth (2000) el papel que usted menciona no hacer la distinción entre" $\pcr(G)$ e $\cr(G)$, y se aplica Hanani–Tutte en la prueba de la travesía lema, que asegura que también tiene por $\pcr(G)$.
El problema es que se puede aplicar Hanani–Tutte para la esfera (y el plano proyectivo), pero no puede aplicar para el toro. Para superficies de género $\geq4$ es que sabe que es falsa, ver Fulek y Kynčl (2019). Esto significa que el toro es realmente del "entre".
Edit: Añadir las referencias
Bojan Mohar (1995): Problema mencionado en la sesión especial sobre Topológica de la Teoría de grafos, Mathfest, Burlington, Vermont. (cita de: L. A. Székely (2016): Frigyes de la Fábrica de Ladrillos Problema: El Estado de las Conjeturas de Zarankiewicz y la Colina. En: R. Gera et al. (eds.)(2016): la Teoría de grafos, el favorito de las conjeturas y problemas abiertos. 1.)
Hanani–Tutte Teorema de https://en.wikipedia.org/wiki/Hanani%E2%80%93Tutte_theorem
Radoslav Fulek y Jan Kynčl (2019): Contraejemplo a una Extensión de la Hanani–Tutte Teorema sobre la Superficie de Género 4. Combinatorica, 39(6):1267-1279
Suponiendo una inédita Ramsey-tipo de resultado por Robertson y Seymour acerca de Kuratowski menores de edad [FK18, Reivindicación 5], que ahora es "folclore" en el gráfico de menores de edad, de la comunidad, un asintótica variante de la travesía lema, $\operatorname{cr}(G)\ge \Omega(e^3/n^2)$, es cierto incluso para el par de cruzar número en una superficie firme, como un toro.
Con Radoslav Fulek [FK18, Corolario 9] hemos demostrado que [FK18, Reivindicación 5] implica un aproximado de versión de la Hanani–Tutte teorema sobre superficies orientables. En particular, [FK18, Reivindicación 5] implica que hay una constante $g$ tal que para cada gráfico de $G$ que puede ser dibujado en el toro con cada par de independiente bordes de cruzar un número par de veces, $G$ puede ser dibujado sobre la superficie orientable de género $g$ sin cruces. Esto le da un límite superior $3n + O(g)$ en el número de aristas de cada gráfico de $G$, y esto puede ser usado en la prueba probabilística de la travesía lema, como se describe en la página. 5-6 de Marcus Schaefer de la encuesta [S20], mencionado en Claus Dollinger la respuesta. Véase también [SSSV96, Teorema 4.1].
Referencias:
[FK18] https://dx.doi.org/10.4230/LIPIcs.SoCG.2018.40, https://arxiv.org/abs/1803.05085 - R. Fulek y J Kynčl, El $\mathbb Z_2$-género de Kuratowski menores de edad
[SSSV96] https://doi.org/10.1007/BF02086611 - F. Shahrokhi, L. A. Székely, O. Sýkora y I. Vrt o, Dibujos de gráficos en superficies con pocos cruces, Algorithmica 16, 118-131 (1996)
[S20] https://doi.org/10.37236/2713 - M. Schaefer, El Gráfico Cruce de Número y sus Variantes: Una Encuesta de La Revista Electrónica de la Combinatoria, DS21: 14 de Febrero de 2020.
@user161819 yo quería hacer un comentario, pero lo tengo muy largo, por lo que poner como respuesta. Pero por favor, tome sólo como un comentario para más adelante, una vez que todo está terminado:
Si entiendo tu comentario a mi respuesta correctamente, usted es el objetivo de cambiar su algoritmo para el toro por lo que funciona con ${\rm cr}(G)$. Creo que todo el MO de la comunidad es mantener los dedos cruzados, que desean que usted puede completar con éxito todo el tiempo!
Mirando el horizonte, quería hacer una sugerencia para usted. Una vez que usted ha cambiado su toro algoritmo y completó su tesis, tendrá, de hecho, dos de los algoritmos en sus manos para que el toro: El antiguo, basado en el ${\rm pcr}(G)$ y la nueva basada en ${\rm cr}(G)$. Yo estoy diciendo lo obvio aquí, dos de ellos, que realmente puede ser fructífero para la investigación futura.
(1) Evidentemente, sus dos algoritmos podría apoyar la investigación sobre el big abierta la cuestión de si ${\rm pcr}(G)\stackrel{\rm ?}{=}{\rm cr}(G)$ o no. Ellos podría producir la evidencia experimental, ideas, y opiniones para un a prueba de futuro de igualdad, o un contraejemplo. (De nuevo, estoy diciendo lo obvio aquí.)
(2) A realmente a la presión de prueba ${\rm pcr}(G)\stackrel{\rm ?}{=}{\rm cr}(G)$ sobre el toro, sería interesante probar también la mejor conocidos hasta la fecha límite inferior de ${\rm cr}(G)$ $$\frac{1}{29}\frac{e^3}{n^2}$$ for graphs with $e>7n$. Este límite inferior es de Eyal Ackerman (2019): "En topológica de los gráficos en la mayoría de los cuatro cruces por el borde", Geometría Computacional, 85: 101574, 31, doi:10.1016/j.comgeo.2019.101574 (probablemente se den cuenta de el artículo de la Wikipedia que usted ha citado).
Creo que su pregunta y todo este tema es realmente importante. László Székely, llama a uno de los "problemas fundamentales" y dedica toda una sección a la que en su artículo Frigyes de la Fábrica de Ladrillos Problema: El Estado de las Conjeturas de Zarankiewicz y la Colina. En: R. Gera et al. (eds.)(2016): la Teoría de grafos, el favorito de las conjeturas y problemas abiertos. 1.)
Por ahora, los dedos cruzados para que usted pueda completar su tesis en el tiempo!
