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

Question

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.

Answer 1

En primer lugar, debo decir que no sé nada de los logros de la teoría de las categorías. Hasta ahora, no he podido descubrir ningún teorema que demuestre algo en, digamos, combinatoria, utilizando la teoría de categorías de manera esencial. (Se han dado pistas en algunas respuestas a esta pregunta pero aún no he tenido tiempo de seguirlos).

Además, tengo que admitir que no conozco lo suficiente la historia, por lo que no puedo afirmar que los siguientes puntos sean realmente logros de un punto de vista "categórico" sobre los objetos combinatorios. Se puede argumentar que no se necesita un lenguaje categórico para enunciar estos conceptos, y me parece que Bergeron, Labelle y Leroux lo han evitado conscientemente. Sin embargo, creo que el "origen" de las ideas es de espíritu "categórico".

1) Yo diría que el concepto de igualdad de las especies ordinarias y, en relación con ello, su descomposición molecular es algo muy importante por derecho propio, simplemente porque es hermoso. No estoy seguro de que este concepto se haya explotado plenamente en un sentido práctico. Posiblemente sea difícil de explotar porque muy a menudo nos encontramos con estructuras que realmente no están etiquetadas. De vez en cuando leo sobre el deseo de clasificar los objetos contados por los números catalanes: hay poco que hacer con las especies, porque su ecuación definitoria es algebraica. (Supongo que esto no excluye la existencia de un objeto etiquetado interesante con tipos de isomorfismo que se cuenten por los números catalanes, si conoces alguno, ¡compártelo, por favor!)

2) estrechamente relacionado con el punto anterior, es la forma muy estructurada de contar bajo la acción del grupo. Nils de Bruijn escribió que "este tipo de teoría de la enumeración es una cuestión de exposición y organización de cosas que en esencia son triviales". En este sentido, creo que en muchos casos, sobre todo las especies multivariantes, son la herramienta adecuada. Un ejemplo concreto: "¿cuántas posibilidades hay de meter dos bolas rojas, dos azules y cuatro verdes en una caja redonda y tres cuadradas?". Sí, es fácil, pero con las especies es trivial: queremos el coeficiente de $[R^2B^2G^4]$ en la serie de tipo isomorfismo correspondiente a $E_1(E(R+B+G)) E_3(E(R+B+G))$ . De nuevo: Me gustaría subrayar que las especies dan estructura al problema, y me parece que esto está en el corazón del "pensamiento categórico", incluso si no hay una teoría de la categoría involucrada.

3) existe al menos una operación útil sobre las especies, que se produce de forma muy natural, a saber, la composición funtorial.

4) este punto es más una pregunta que una respuesta: ya se han mencionado los operados, ¿alguien sabe qué Funtores monoidales, especies y álgebras de Hopf de Marcelo Aguiar y Swapneel Mahajan se trata? Tal vez eso responda "realmente" a la pregunta original...

Answer 2

Una línea más de respuesta invocaría de nuevo a Rota:

"¿Qué se puede demostrar con el álgebra exterior álgebra exterior que no se pueda demostrar sin sin ella?" Cada vez que se oye esta pregunta sobre alguna nueva pieza de matemática, tenga la seguridad de que es que está en presencia de algo importante. algo importante. En mis tiempos, he he oído repetirlo para las variables aleatorias variables aleatorias, la teoría de Laurent Schwartz distribuciones, los ídolos y los esquemas de Grothendieck, por mencionar sólo algunos. Una réplica adecuada podría ser: "Tienes razón. No hay nada en matemáticas de ayer que no pudiera demostrarse también sin ella. Exterior álgebra exterior no está destinada a demostrar viejos hechos antiguos, sino para revelar una nueva mundo. Revelar nuevos mundos es tan una empresa matemática que vale la pena como probar viejas conjeturas. (Pensamientos Indiscretos, p.48, Birkhauser, 1997).

Para ver un par de nuevos mundos posibles gracias al concepto de especie, véase:

1) M. Fiore, N. Gambino, M. Hyland y G. Winskel. The cartesian closed bicategory of generalised species of structures. Journal of the London Mathematical Society, 77(2) (2008), 203-220.

2) J. Baez et al. sobre tipos de cosas (nota: llaman a las especies "tipos de estructura").

Answer 3

Para ver un ejemplo concreto de especies aplicadas a un problema de enumeración bastante difícil (el recuento de bloques bipartitos), véase mi artículo con Andrew Gainer-Dewar, Enumeración de grafos bipartitos y bloques bipartitos , Electronic Journal of Combinatorics, Volume 21, Issue 2 (2014) Paper #P2.40. Si te lo tomas realmente en serio, podrías comparar nuestro enfoque para contar grafos bipartitos con el de Hanlon.

Answer 4

Dado que la Teoría de las especies también trata del reetiquetado, y los reetiquetados forman grupos de permutación, la Teoría de las especies está muy relacionada con la teoría de los grupos de permutación. ¿Es la teoría de las especies una parte de la teoría de grupos? NO. Y si lo fuera, alguien debería sacarla de ahí y convertirla en una teoría independiente.

Imagínese que alguien quiere escribir un libro que contenga ecuaciones como Part = E(E+), o ese increíble lomo de Joyal sobre la fórmula de Cayley. Entonces el autor debe escribir un montón de cosas de permutaciones, dejando las fórmulas para el último capítulo quizás, y confundiendo al lector: ¿Este libro trata de permutaciones o de otra cosa?

La definición functorial evita todos los problemas de permutación que habría implicado, incluyendo la definición de especies sobre conjuntos vacíos o la noción de copias del conjunto vacío. Un objeto simple como una caja vacía no es probable que sea descrito por el conjunto vacío matemático. De todos modos, si todavía hay problemas con los conjuntos vacíos y las permutaciones vacías, éstos son menos visibles en el lenguaje de los gatos.

Por ello, creo que la principal preocupación de los autores era no recargar la teoría de grupos de permutación, y esto es muy comprensible. Todas las piezas de este mega rompecabezas combinatorio ya se conocían: los anillos de Burnside, el producto de la corona, la fijación de un elemento, los polinomios de Polya sobre las simetrías y las funciones generadoras exponenciales. También creo que cualquier presentación de Especies debería enfatizar de alguna manera la magia del cálculo egf, que es para la Combinatoria lo que el cálculo O y 1 es para la Lógica verdadera y falsa.

Hoy en día, cuando se enumeran muchos f.e.g., cualquiera podría observar algunas relaciones "misteriosas" entre los f.e.g. y podría construir al menos algunos significados mnemotécnicos que aporten cierto orden en las enormes listas de fórmulas. La Teoría de las Especies trata de dar una base científica a esta colección de significados mnemotécnicos. Es como si alguien inventara la geometría sintética clásica después de dos mil años de geometría cartesiana analítica y tratara de fundamentarla bien.

Bibliografía http://www.math.sinica.edu.tw/www/file_upload/mayeh/1989Therelationsbetweenpermutation.pdf Labelle y Yeh en 1987 sobre los grupos de permutación y las especies a todos los fans de Species como yo -> también estoy viendo la página de discusión en wikipedia http://en.wikipedia.org/wiki/Talk:Combinatorial_species