EDICIóN GENERAL
374 meneos
5110 clics
Yaroslav Shitov: Un matemático ruso desmiente una conjetura con más de medio siglo de vida

Yaroslav Shitov: Un matemático ruso desmiente una conjetura con más de medio siglo de vida

Casi coincidiendo con su 30 cumpleaños (fue el pasado 3 de junio), el nombre de Yaroslav Shitov ha aparecido en buena parte de la prensa mundial. Este matemático ruso ha probado que una conjetura con más de medio siglo de vida sobre un problema de teoría de grafos es falsa, dando un contraejemplo, es decir, aportando un caso en el que no se cumple lo que la conjetura predecía que sucedía siempre.

| etiquetas: matemáticas , contraejemplos , teoría de grafos , coloreado de grafos
143 231 4 K 283 cultura
143 231 4 K 283 cultura
Para eso son las conjeturas, para invitar a demostrarlas o refutarlas.

conjetura
Del lat. coniectūra.
1. f. Juicio que se forma de algo por indicios u observaciones.
(...)

demostración
Del lat. demonstratio, -ōnis.
(...)
5. f. Fil. Comprobación, por hechos ciertos o experimentos repetidos, de un principio o de una teoría.

Diccionario de la RAE
#1 Correcto, por eso era una conjetura y no una demostración.
#3 te corrijo: por eso era una conjetura y no un teorema :-) (sin haber leído la noticia)
#34 Un teorema es demostrable formalmente.
#35 pero un teorema no es una demostración :troll:


Na. Olvídalo. Que tenía ganas de tocar un poco las narices :-D
#1 ¿Y? Cualquiera que sepa un poco de matemáticas sabe eso.
Para quienes hayan recorrido un camino hamiltoniano alguna vez, la conjetura era esta:

Dados dos grafos G y H, el número de colores necesario para colorear el grafo producto tensorial G X H es el menor de los colores necesarios para colorear G y H. Y el contraejemplo ha sido encontrar dos grafos G y H tales que su producto tensorial necesita menos colores que los requeridos para colorear tanto G como H

Para una explicación sobre grafos tensoriales en relación a esta conjetura: www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theor
#7 A mi me hablas en cristiano ;)
#12 Lo mismo he pensado <:( :palm:
#7 "Suppose you’re a music teacher who wants to find good duet pairings for the fifth grade concert. You could make a graph whose nodes are the students, with a link between each pair who get along well. And you could make a second graph in which each node is a different musical instrument, with a link between two instruments if you have sheet music for a duet that features them. The tensor product of these two graphs would have one node for each possible pairing of a student and an instrument (say, Alicia on the trombone), and two nodes will be linked whenever the two students in question work well together and the two instruments are compatible."
:clap: :clap: :clap:
#14 En español:
"Supón que eres un profesor de música que quiere encontrar buen emparejamientos para duetos en un concierto de alumnos de quinto curso. Podrías hacer un grafo cuyos vértices son los estudiantes, con una arista entre cada pareja que se lleva bien. Y podrías hacer un segundo grafo en el que cada vértice es un instrumento musical diferente, con una arista conectando dos instrumentos si tienes una partitura de dueto para esos dos instrumentos. El producto tensorial de esos dos…  media   » ver todo el comentario
#26 De trabajo para casa: demostrar, coloreando todos los grafos con el mínimo de colores, que en el ejemplo se cumple la conjetura de Hedetniemi. :-D
#27 En el ejemplo son dos colores, no?

En el contraejemplo del ruso cada grafo tiene 4^100 nodos para probar que se puede hacer con menos.

#RussianFacts :-)
#32 No sé, no soi sientífico. :-P Pero son dos.
#7 Eso en mi barrio es pelea!
De estas cosas que si no las desmientes no descansas... :troll:
Menudas erratas.

<<Por tanto, si encontramos un algoritmo que resuelva de forma eficiente el problema de colorear grafos (con una cantidad de operaciones menor que un cantidad relacionada con el número de vértices del grafo), podemos ir al instituto Clay y reclamar un millón de dólares, porque habremos demostrado que P es distinto a NP, y con ello uno de los célebres problemas del milenio y que llevan asignado ese premio. Si alguno de los lectores tiene el algoritmo pero no entiende

…   » ver todo el comentario
Esto es una pasada de descubrimiento, descubrir una propiedad nueva en los grafos puede suponer un avance enorme en inteligencia artificial.

Estoy deseando echar un ojo al articulo!
#4 arxiv.org/pdf/1905.02167.pdf
No llega a dos páginas y media.
#5 estaba leyendolo ahora mismo, no me habia fijado que estaba mencionado en el articulo (gracias academia de las matematicas).

#8 en este caso concreto es incluso mas relevante, porque el podado de redes neuronales tiene un calculo muy parecido al problema de los colores. Esto es MUY bueno, y me hace pensar como un tio de 30 años puede ser tan bueno en matemáticas hoy día.

PD. Soy de Ciencias de la Computacion, no puedo evitarlo.
#17 Que va, ahora están otra vez de moda con todo lo de Deep Learning.

Por ejemplo, tienes las redes neuronales profundas (DNN) y las redes neuronales adversariales (GAN). Son dos de las técnicas más populares actualmente en investigación y en empresas de tecnología "punta".
#23 No es lo mismo inventar o desarrollar las redes neuronales, que inventar o desarrollar aplicaciones a dichas redes. Y sí, ahora está de moda usar redes neuronales para un montón de cosas distintas.
#23 hombre las GAN son del 2014, pocos añitos me parecen
#17 tanto es así que hoy día se llevan como tres asignaturas en los grados de informática y matemáticas :palm:
#22 yo soy de la época del wordpad. Estoy en el lado de los profes.
#50 El respecto es mutuo. :hug:
#22 ¿El cálculo también está pasado de moda? ¡Valiente símil!
#17 lo que tiene hablar sin tener ni idea
#9 No acabo de ver la aportación práctica.

Ha encontrado un caso particular para el cual no se da lo que proponía la conjetura. Un ejemplo de un caso particular a priori no parece especialmente útil para aplicarlo de forma general.

Si alguien estaba basándose en esa conjetura para operar lo que debe hacer es seguir como está si esos casos particulares son demasiado excepcionales para ser relevantes o directamente dejar de usarlo. Lo cual no parece a priori un avance si no más bien un retroceso.

Y si por contra no se estaban basando en esa conjetura no tiene sentido hacerlo ahora.

Otra historia sería que a partir de este caso particular alguien generalizase algo diferente y útil, pero no parece que sea lo que aporta este meneo.
#25 creo que #36 lo explica mucho mejor de lo que yo podría.
#25 En mi opinión hay una conclusión muy importante :

Bajo determinadas circunstancias, un grafo producto tensorial G.H tiene una solución más eficiente que sus grafos de origen de forma independiente.

Esto significa que puede realizarse una poda de forma más eficaz en un grafo. Los grafos son parte fundamental de la teoría de Algoritmos que gobiernan la computación...

Y el tío lo ha sacado a papel y lápiz, con un método de generación de grafos QUE SIEMPRE cumplirán la propiedad. Es un matemático muy bueno...
#5 Es lo que tienen los contraejemplos, si la conjetura no exige demasiadas condiciones dentro de unos conceptos ya de por sí oscuros (no estamos hablando de grupos gigantescos de Lie).
#4 y para informáticos en general.
Si hay grafo hay algiritmo que se beneficia.
#4 ¿Cómo un algoritmo? Ecuación ya pensada, determinada, calculada, constante en su disposición. Puede interferir en el desarrollo de la inteligencia artificial (que es no constante y consiste en desarrollarse, calcularse y determinarse como cualquier otra inteligencia).
#4
Querrás decir descubrir que los grafos NO tienen una propiedad...

No se qué aplicaciones puede tener descubrir que una posible propiedad en realidad no se cumple siempre.
#30 hombre utilidades tiene muchísimas porque hasta antes de la demostración se daba por hecho que si se cumplía. Si hubiera una conjetura que dijera que se puede colgar un piano de cola del techo con un hilo del grosor de un cabello humano todo el mundo guardaría sus pianos de cola colgando del techo encima del sofá y se sentaría debajo tan tranquilamente, que alguien demuestre que en una determinada circunstancia el piano se cae tú si quieres sigue tranquilito en el sofá que yo o cambio el sofá de sitio o guardo el piano en otro lado. Ahora aplícalo a casos prácticos donde una vez encontrado el punto más óptimo según el teorema han dejado de buscar si se podía optimizar más porque según la conjetura es imposible
#30 de hecho se ha descubierto!

Bajo determinadas circunstancias, un grafo producto tensorial G.H tiene una solución más eficiente que sus grafos de origen de forma independiente.
#40 No comprendo de qué manera eso que acabas de decir responde a mi comentario #30

¿Puedes explicarlo un poco más?
#42 me refiero a que está claro que el paper ha definido una nueva propiedad de los grafos.
#43
Ah, claro, la propiedad de no tener la propiedad que se pensaba ¿es eso?

Sigo sin saber qué posibles aplicaciones puede tener... Quizá que hasta ahora se daba por hecho o por supuesto que el número de colores era cierto número y ahora al saber que puede ser menor puede intentarse una solución más óptima.
#44 Exacto. Existe un parametro llamado arista-coloracion, que esta ligado al grado maximo de un grafo. Si de repente encontramos una manera de transformar un grafo de forma que se reduce su grado, optimiza la resolucion.

Si a este descubrimiento, le siguiera un procedimiento para generalizar la reduccion de grado de un grafo, estariamos ante un via para hallar la solucion a la conjetura P=NP, puesto que un grafo de colores es un problema NP.
#45

"estariamos ante un via para hallar la solucion a la conjetura P=NP, puesto que un grafo de colores es un problema NP."

Pero para eso se necesitaría no solamente que un grafo de colores sea NP sino que todo problema NP pueda reducirse o sea isomorfo a un grafo de colores ¿no te parece?
#47 No entiendo a que tiene que ver el isomorfismo aquí, salvo que estés pegándome un vacile, pero en todo caso un grafo isomorfo tiene una solución determinista,por lo que no está sujeto a conjeturas.
La conjetura de Hedetniemi propone un escenario distinto.

De todas maneras, aclaro: Todo avance en la teoría de grafos sería una vía de investigación de los problemas NP, NO una solución a los problemas NP. Me temo que hoy día no tenemos herramientas para llegar a ese punto.
#47 Me suena que es NP-Completo y eso significa que todos los problemas NP son reducibles a ese. Hablo de memoria.
#44 Añado, los problemas de colores tienen dos aplicaciones practicas muy relevantes, la asignacion de registros en los procesadores, y la optimizacion (poda) de redes neuronales y redes GAN.
what a Shit
no entendí
comentarios cerrados

menéame