web analytics

Archivo de agosto 31st, 2013

La conjetura de Gian-Carlo Rota, resuelta

Esta semana se ha anunciado en diferentes medios de comunicación que los investigadores Jim Geelen (University of Waterloo, Canadá), Bert Gerards (Centrum Wiskunde & Informatica, Países Bajos) y Geoff Whittle (Victoria University, Wellington, Nueva Zelanda)  habían demostrado la conjetura de Gian-Carlo Rota, tras 15 años de intenso trabajo. Aunque este largo trabajo de colaboración no ha terminado aún, ya que quedan aún por delante años de trabajo para escribir los detalles, ya hay disponible una versión del artículo en Internet. Marta Macho, de la Universidad del País Vasco (EHU-UPV), presenta el resultado.

Gian-Carlo Rota en el Congreso de Niza, 1970

En el Congreso Internacional de Matemáticos (ICM en sus siglas inglesas) de Niza de 1970, el matemático y filósofo Gian-Carlo Rota conjeturó:

La familia de matroides que pueden representarse sobre un cuerpo finito tiene una cantidad finita de menores excluidos.

En el blog The Matroid Union se explican con detalle todas las nociones involucradas en el enunciado de esta conjetura,  enmarcada  en el área de la combinatoria. De manera informal, una matroide es una estructura que captura y generaliza la noción de independencia lineal en un espacio vectorial.

Hassler Whitney introdujo en 1935 la noción de matroide [On the abstract properties of linear dependence, Amer. J. Math., 57, 509-533]  buscando una relación entre el álgebra lineal y la teoría de grafos, basada en el concepto de dependencia lineal.

……………………………………………

Manuel de León lo explica de la siguiente manera:

El concepto de matroide es muy simple y el siguiente ejemplo lo muestra claramente.

Consideremos la matriz:

 

y etiquetemos las columnas como C1, C2, C3, C4, C5, C6 y C7.

Ahora buscamos todas las colecciones de columnas entre estas 7 que contengan como mucho tres de esas columnas (la matriz es 3×3) y que estas sean linealmente independientes. Podemos eliminar por supuesto la séptima columna porque está formada por ceros.

Tras un sencillo calculo, encontramos que todos los conjuntos de tres columnas, excepto los subconjuntos {C1, C2, C4}, {C2, C3, C5}, {C2, C3, C6} y todos aquellos que contengan las columnas C5 y C6 (porque estas son iguales y por lo tanto dependientes entre si), son linealmente independientes. Consideramos el subconjunto I de todas esas colecciones de columnas y también el conjunto E = {C1, C2, C3, C4, C5, C6}. El par (E, I) es un matroide.

Lo que Whitney hizo después fue analizar las propiedades fundamentales de este tipo de estructuras (el conjunto I no es vacío, es hereditario en el sentido de que cualquier subconjunto de un elemento de I está tambien en I, y una tercera propiedad que nos dice que dados dos elementos de I que difieren en una unidad en su cardinalidad, se le puede añadir un elemento de la diferencia de los dos subconjuntos al menor y el resultado sigue siendo un elemento de I).

Un aspecto curioso de la noción de matroide concierne precisamente a este nombre. Rota le dio el nombre de geometría a este concepto, e intentó que ese nombre se impusiera. De hecho,en 1973 escribió: ”Se han usado varios nombres en lugar de geometría; estilísticamente van desde lo grotesco a lo patético. El único (término utilizado en lugar de geometría) que sobrevive es “matroid”, que sigue siendo utilizado en reductos de la tradicionalista Commonwealth Británica”. Pero parece que el termino matroide se ha impuesto.

……………………………………………

Desde entonces, la noción de matroide se ha generalizado, y en particular, la conjetura de Rota trata sobre las obstrucciones a la representabilidad de esta estructura sobre cuerpos finitos.

La conjetura se había resuelto en algunos casos particulares. Por ejemplo, el famoso matemático William T. Tutte demostró en 1965 que las matroides binarias –representables sobre el cuerpo de dos elementos– tienen un único menor excluido. La resolución del caso de matroides sobre el cuerpo con 4 elementos supuso para sus autores –J. Geelen, M. H. Gerards y A. Kapoor– la concesión del Premio Fulkerson en 2003.

Jim Geelen, Bert Gerards y Geoff White

Geoff Whittle ya había revelado a unos colegas en una reciente visita al Reino Unido, que los elementos fundamentales de la prueba estaban superados. Este largo trabajo de colaboración no ha terminado aún: según confesaba en una entrevista, quedan aún por delante años de trabajo para escribir los detalles.

http://youtu.be/Lw8D15amE_4

Entrevista a Geoff White

En el preprint Structure in Minor-Closed Classes of Matroids, Geelen, Gerards y White describen los ingredientes involucrados en el enunciado de la conjetura.

Más información:

[1] Gian-Carlo Rota, Combinatorial theory, old and new, Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3, Gauthier-Villars, 229–233, 1971.

[2] Rota’s Conjecture proven!, The Matroid Union, 22 de agosto de 2013 (con extensas explicaciones sobre la conjetura)

[3] Victoria researcher solves 40 year-old math problem, Victoria University, 15 de agosto 2013

[4] Rota’s Conjecture: Researcher solves 40-year-old math problem, Phys. Org, 15 de agosto de 2013

[5] CWI researcher proves famous Rota’s Conjecture, CWI, 22 de agosto 2013

[6] Waterloo mathematician solves 40-year-old problem, University of Waterloo, 28 de agosto de 2013

_____________________________

Marta Macho-Stadler es Profesora del Departamento de Matemáticas (Facultad de Ciencia y Tecnología) de la Universidad del País Vasco-Euskal Herriko Unibertsitatea.

 

Etiquetas:
Categorias: General