05/12/2019, 10:29:18 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Resuelta la conjetura de la sensibilidad con métodos elementales  (Leído 381 veces)
0 Usuarios y 1 Visitante están viendo este tema.
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 800



Ver Perfil
« : 07/07/2019, 07:59:57 am »

Hola,

Hace una semana apareció un preprint donde el matemático H. Huang da una demostración de la conjetura de la sensibilidad (sensitivity conjecture). Este era uno de los problemas abiertos más importantes en la teoría de complejidad computacional (más concretamente, en complejidad de funciones booleanas), y llevaba abierta 30 años.

Esta conjetura es equivalente al siguiente problema de teoría de grafos. Definimos el grafo [texx]Q_n[/texx] como aquél que sus vértices son todas las sucesiones de longitud [texx]n[/texx] formadas por ceros y unos (por tanto tiene [texx]2^n[/texx] vértices) y dos vértices están unidos por una arista si sus sucesiones de ceros y unos asociadas difieren exactamente en un número. A [texx]Q_n[/texx] se le suele llamar el grafo hipercubo, porque sus vértices y aristas se corresponen con los vértices y aristas de un hipercubo de dimensión [texx]n[/texx]. Por ejemplo, en la imagen se ven [texx]Q_1,Q_2,Q_3[/texx]:



Lo que ha demostrado Huang es que si tomamos un subgrafo [texx]H[/texx] inducido con [texx]2^{n-1}+1[/texx] vértices (esto es, el subgrafo de [texx]Q_n[/texx] formado por los [texx]2^{n-1}+1[/texx] vértices elegidos y todas las aristas que unen esos vértices en [texx]Q_n[/texx]), entonces existe algún vértice de H del que salen por lo menos [texx]\sqrt{n}[/texx] aristas (a otros vértices de [texx]H[/texx]). Está claro que con un subgrafo de [texx]2^{n-1}[/texx] aristas no basta, pues el subgrafo con vértices [texx](10 \dots 0), (01 \dots 0), \dots (00 \dots 1)[/texx] tiene [texx]2^{n-1}[/texx] vértices pero ninguna arista.

Esto no sería demasiado destacable (al fin y al cabo prácticamente todos los días se resuelven conjeturas, aunque quizás no tan importantes ni que lleven tanto tiempo abiertas) si no fuera por cómo es la prueba.
Normalmente, cuando alguien demuestra una conjetura famosa, a la que le han intentado echar mano muchos expertos en el campo, la demostración suele ser compleja, técnica, larga y difícil de entender para alguien que no esté familiarizado con el campo.
Lo realmente remarcable en este caso es que el paper con la demostración ocupa 6 páginas, la demostración en sí (incluyendo lemas) ocupa página y media, y usa técnicas completamente elementales. Cualquiera que haya cursado álgebra lineal y sepa qué es un vector propio de una matriz puede leer y entender la prueba.

Esto hace plantearse cuántas demostraciones elementales de resultados importantes se les habrán pasado a los expertos y están ahí esperando a que alguien las descubra,

PD: Añado el link al artículo, que se me olvidó. https://arxiv.org/pdf/1907.00847.pdf

* hypercube_graphs.png (15.46 KB - descargado 118 veces.)
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
Fernando Moreno
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 198


Ver Perfil
« Respuesta #1 : 07/07/2019, 12:11:04 pm »

Hola,

Gracias geómetracat por la noticia. Muy interesante por lo que comentas. Yo pienso que las largas demostraciones muy técnicas están condenadas a ser simplificadas. Otra cosa es que se puedan hacer con matemáticas elementales. Una de las claves, pienso, es la iterdisciplinariedad y la divulgación. En matemáticas la divulgación no es como en otras materias, es algo difícil y de mucho mérito. Contar una demostración, "con otras palabras" y sin desnaturalizarla vale mucho. Cada punto de vista diferente a la hora de decir eso mismo aporta su grano de arena para que en un futuro alguien pueda llegar a otra demostración por un camino distinto. También está la motivación. Un divulgador que además motive aporta un valor añadido más para que alguien lo intente. Hay varios ejemplos en internet. Y este Foro es uno de ellos. Pienso que debería valorarse más la divulgación en matemáticas. Realmente es en sí misma "matemáticas" y yo diría aún más: "investigación en matemáticas".

Un cordial saludo,
En línea

  El mal es malo también para sí mismo. Por eso, a la larga, sólo puede triunfar el bien. Y por eso también la libertad es buena y deseable..  F. Moreno 
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.599



Ver Perfil
« Respuesta #2 : 07/07/2019, 12:16:40 pm »

Gracias, geómetracat.

Esta cuestión, la de las demostraciones elementales que mencionas, ha sido muy comentada en varios hilos de este foro, muy especialmente en los relativos al Último Teorema de Fermat; donde parece prácticamente imposible que pueda existir una demostración sencilla. Muchos se alegrarán de este resultado (yo creo que todo el mundo).

*Por lo que dices, yo debería entender esta prueba; la miraré a ver... pero no sé, no sé...

Saludos.   
En línea

martiniano
Pleno*
*****

Karma: +2/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 934


Ver Perfil
« Respuesta #3 : 07/07/2019, 12:40:53 pm »

Hola.

Sí, sorprendente noticia. Estaría bien echarle un vistazo a esa publicación. Yo también tengo curiosidad, la verdad. No obstante, no acabo de entender bien el enunciado de la conjetura y no he encontrado nada por internet (soy bastante torpe buscando en la red, todo hay que decirlo). Es decir:

Sea [texx]Q_n[/texx] el grafo hipercubo de orden [texx]n[/texx]. Si se toma un subgrafo cualquiera [texx]H[/texx] con [texx]2^{n-1}+1[/texx] vértices, entonces existe algún vértice del que salen [texx]\sqrt[ ]{n}[/texx] aristas o más.

Se me escapa algo, ya que si se toma [texx]H[/texx] un subgrafo que contiene los vértices que sean pero ninguna arista, [texx]H[/texx] no cumple el enunciado.

Un saludo.
En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 800



Ver Perfil
« Respuesta #4 : 07/07/2019, 12:50:13 pm »

Hola.

Sí, sorprendente noticia. Estaría bien echarle un vistazo a esa publicación. Yo también tengo curiosidad, la verdad. No obstante, no acabo de entender bien el enunciado de la conjetura y no he encontrado nada por internet (soy bastante torpe buscando en la red, todo hay que decirlo). Es decir:

Sea [texx]Q_n[/texx] el grafo hipercubo de orden [texx]n[/texx]. Si se toma un subgrafo cualquiera [texx]H[/texx] con [texx]2^{n-1}+1[/texx] vértices, entonces existe algún vértice del que salen [texx]\sqrt[ ]{n}[/texx] aristas o más.

Se me escapa algo, ya que si se toma [texx]H[/texx] un subgrafo que contiene los vértices que sean pero ninguna arista, [texx]H[/texx] no cumple el enunciado.

Un saludo.

Fallo mío. El problema no se refiere a cualquier subgrafo sino a subgrafos inducidos. Es decir, a los subgrafos que resultan de tomar [texx]2^{n-1}+1[/texx] vértices cualesquiera de [texx]Q_n[/texx] y que tienen como aristas las mismas aristas que en [texx]Q_n[/texx] entre los vértices escogidos.
Gracias por darte cuenta del error.

He añadido el link al artículo en el primer post.
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!