81 votos

¿Cuáles son algunos ejemplos de usos interesantes de la teoría de las especies combinatorias?

Esta es una pregunta que ya me he hecho un par de veces, pero su aparición en MO está un poco motivada por este hilo y el comentario de sigfpe a la respuesta de Pete Clark.

A menudo he oído decir que las especies combinatorias son maravillosas y demuestran que la teoría de categorías también es útil para la combinatoria. Me gustaría que me sacaran de mi escepticismo.

No he leído el documento original de Joyal de 82 páginas sobre el tema, pero hojear un par de libros no me ha ayudado a ver lo que me estoy perdiendo. La página de Wikipedia, que seguramente es una medida injusta de la profundidad y los usos de la teoría, refuerza mi escepticismo más que nada.

Como primer paso en mi creciente apreciación de las ideas categóricas en campos que me resultan familiares (la lógica puede ser la siguiente), me gustaría conocer algunos usos de las especies combinatorias para demostrar cosas en combinatoria.

Busco ejemplos en los que haya una clara ventaja en su uso. Para alguien cuya lengua materna no es la teoría de categorías, no es útil decir simplemente que "las estructuras combinatorias son funtores, porque permutar los elementos de un conjunto A da una permutación de los órdenes parciales sobre A". Esto es como esperar que las analogías del béisbol aumenten la comprensión del fútbol de un brasileño. De hecho, si me preguntaran al azar en la calle, preferiría usar el razonamiento combinatorio para entender las categorías finitas que usar las categorías de conjuntos finitos para entender la combinatoria.

Añadido para clarificar: En mi (limitada) lectura de las especies combinatorias, hay bastantes cosas que son combinatorias. El objetivo de mi pregunta es entender cómo el categórico parte está ayudando.

44voto

David Precious Puntos 4429

Empecemos por el principio. El principal libro de texto sobre las especies es celui-ci por Bergeron, Labelle y Leroux, todos ellos grandes expertos en la materia. Aunque no quiera leer el libro, lea el introducción de G.-C. Rota (que es interesante, esclarecedor y relativamente corto. En él, Rota escribe:

"Me atrevo a hacer una predicción sobre la futura aceptación de este libro. Al principio, los veteranos fingirán que el libro no existe. Esta pretensión durará hasta que un número suficiente de combinadores jóvenes publiquen artículos en los que se resuelvan problemas interesantes utilizando la teoría de las especies. Con el tiempo, se resolverá un problema importante en el lenguaje de las especies, y a partir de ese momento todo el mundo tendrá que tomar nota."

Han pasado 13 años desde que se escribieron estas palabras (casi hasta el día de hoy), así que quizás sea el momento de volver a revisar esta predicción. La parte del "gran problema" claramente no funcionó. Se puede argumentar que es demasiado pronto para juzgar. Tal vez. Tal vez no. La primera parte, sobre "suficientes combinadores jóvenes", es más interesante y probablemente discutible. Hay suficientes personas que utilizan y hacen referencia al libro: tiene más de 300 citas en GoogleScholar. Y si se observan estas citas, queda claro que el libro tiene una amplia influencia en una gran variedad de campos: el lenguaje y la filosofía de las especies son claramente útiles.

Por otro lado, en comparación con la "competencia", la teoría de las especies no sale tan bien parada. "Combinatorial Enumeration" de Goulden & Jackson y "Enumerative Combinatorics" de Stanley han sido citados unas 1.000 veces cada uno (sí, ambos son más antiguos, pero aun así). Si nos alejamos un poco del campo, "Probabilistic Method" de Alon & Spencer ha sido citado más de 3.000 veces...

Mis conclusiones: la respuesta a su pregunta es tanto Sí como No. La teoría de las especies es claramente útil, pero más bien como un buen lenguaje a utilizar, o un principio rector de qué caminos tomar y de cuáles mantenerse alejados. Cuando se trata de problemas "prácticos" explícitos, la gente parece preferir herramientas más directamente aplicables. Yo compararía este fenómeno con la influencia de la teoría de la complejidad en la combinatoria enumerativa: sea lo que sea lo que estés enumerando, aunque tus problemas no sean algorítmicos y estén en un entorno combinatorio muy clásico, sigue siendo útil saber qué es #P-completo , simplemente porque esto le da un punto de vista diferente sobre los objetos que está enumerando, y a veces también puede ahorrarle un poco de tiempo al sugerir que el problema podría ser demasiado general y, por lo tanto, no tener una solución explícita.

30voto

idbrii Puntos 482

La composición de especies está estrechamente relacionada con la composición de colecciones simétricas de espacios vectoriales ("módulos S"), que es un ejemplo notable de una categoría monoidal que todo el mundo que se ha encontrado alguna vez con las operadas ha utilizado necesariamente. La aplicación de las ideas procedentes de esta interpretación de la categoría monoidal tiene varias consecuencias también para la combinatoria. Por ejemplo, los artículos de Bruno Vallette sobre los posets de partición ( aquí y aquí ): Creo que ya la descripción del $S_n$ La acción sobre la homología superior de la red de partición habitual era difícil de explicar desde el punto de vista de la combinatoria, y para muchas otras redes sería imposible sin el punto de vista de la dualidad de Koszul.

18voto

Ed Haber Puntos 1121

Pietro, si no lo has hecho ya, deberías leer el artículo de Joyal. (No entiendo por qué expresas tu escepticismo antes de haber mirado las fuentes primarias).

Si hay que destacar una sola aplicación de las especies de este maravilloso artículo, es la demostración de Joyal del teorema de Cayley. (Esta prueba fue destacada en Pruebas de EL LIBRO .) Pero éste es sólo uno de los tesoros del periódico que esperan a quienes se tomen la molestia de leerlo.

Gran parte del arte del pensamiento combinatorio (al menos en la combinatoria enumerativa) consiste en saber dibujar correctamente, y la teoría de las especies puede verse como un paso hacia la conversión de ese arte en ciencia, al formalizar directamente las operaciones sobre las estructuras que están implícitamente codificadas por las técnicas de las funciones generadoras. En otras palabras, las operaciones funcionales básicas sobre las funciones generadoras exponenciales se elevan a operaciones funcionales sobre las especies. En algún nivel, los combinadores debían conocer estas ideas, pero la teoría de las especies sirve para formalizarlas a la luz del día, y nada menos que un combinador como Zeilberger ha encontrado en las especies una importante fuente de inspiración.

10voto

Vetle Puntos 413

La perspectiva categórica te dice por qué los egf tienen $n!$ ¡s en el denominador! Se puede pensar que una especie describe un "groupoide graduado", donde el grado de $n$ es el grupúsculo formado por la acción de $S_n$ en los conjuntos correspondientes. El cardinalidad del grupo de un grupo finito $G$ actuando sobre un conjunto finito $X$ es sólo $\frac{|X|}{|G|}$ por lo que la "cardinalidad grupal graduada" de una especie es precisamente su egf.

En casos como el de los números catalanes donde la función generadora natural es ordinaria, lo que ocurre es que la acción de $S_n$ es gratis. Por ejemplo, la especie correspondiente a los números catalanes corresponde realmente a los árboles binarios enraizados etiquetados, y $S_n$ actúa en las etiquetas. El cociente resultante cuenta con árboles binarios enraizados no etiquetados, por lo que la función generadora parece ordinaria.

9voto

maclema Puntos 5959

Antes de aprender sobre las especies no entendía por qué a veces se usan funciones generadoras exponenciales y a veces ordinarias. Ahora lo entiendo: ¡para las especies hay que usar funciones generadoras exponenciales!

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X