18 votos

Intersección entre la teoría de categorías y la teoría de grafos

Soy un estudiante de posgrado que ha pasado mucho tiempo trabajando con categorías (categorías modelo, categorías derivadas, categorías trianguladas...), pero antes me encantaba la teoría de grafos y siempre he tenido un hueco en mi corazón para ella. Este semestre estoy tomando un curso de teoría de grafos y por primera vez veo conexiones con la teoría de categorías en forma de la grafo dirigido subyacente de una categoría (los objetos se convierten en vértices, y ponemos una arista $(A,B)$ si hay un morfismo $A\rightarrow B$ ).

Me gustaría saber más sobre los lugares en los que la teoría de grafos ha informado a la teoría de categorías.

Una pregunta que puede plantearse en este sentido es si un gráfico dado podría ser el gráfico subyacente de una categoría. Samer Allouch ha respondido a esta pregunta en su tesis sobre grafos finitos. Lamentablemente, la tesis está en francés y no puedo entenderla. He aquí un buen n-Categoría Puesto de café sobre esto. En ese post alguien pedía una explicación de los resultados o ideas en inglés, pero nunca se dio. Me encantaría saber de esto si alguien aquí lo sabe, pero mi pregunta es más general. Dado que la mayoría de las categorías que conozco y entiendo no son finitas (ni siquiera pequeñas), me pregunto si existen trabajos que relacionen las categorías grandes con la teoría de grafos.

Como esto es muy vago, se me ocurrieron algunas preguntas concretas. Sin embargo, si todo lo que recibo son peticiones de referencias que no tienen nada que ver con estas preguntas, me alegraré igualmente. En particular, me encantaría que me dijeran en qué ocasiones se han planteado y respondido preguntas similares a las siguientes, o que me recomendaran un libro de texto sobre teoría de categorías que se centre en el grafo subyacente más de lo que lo hace Maclane.

1) ¿Alguien ha clasificado los (sub)gráficos que corresponden a repleto ¿subcategorías? Por ejemplo, ¿existe una prueba puramente teórica de grafos para saber si un subgrafo $\mathcal{H}$ de $G$ subyace una subcategoría repleta $\mathcal{D}$ de $\mathcal{C}$ ?

Esto es lo que puedo decir hasta ahora sobre este problema: para cada objeto no isomorfo en $\mathcal{D}$ obtendrá un gráfico completo en $H$ . Los morfismos de composición garantizan que si hay alguna flecha de un vértice a otro vértice en un subgrafo completo diferente, entonces habrá flechas de todos los vértices del primer subgrafo completo a todos los del segundo. Así que $H$ tendrá que parecerse a una unión disjunta de grafos completos, donde completo aquí significa que para cada dos vértices hay una arista al menos en un sentido entre ellos. Una de las razones por las que me resulta difícil entender esto es que estamos tratando con subgrafos de grafos incontables en los que los vértices pueden tener grados incontables. Puedo resolverlo restringiéndome a clases de isomorfismo de objetos, pero no estoy seguro de que sea una buena idea. Me encantaría que los más versados en teoría de categorías me dijeran cuáles son los pros y los contras de restringir a clases de isomorfismo. Nótese que la versión de esta pregunta para subcategorías completas se responde con "subgrafos inducidos", por lo que parece que no hay esperanza de clasificar subcategorías gruesas u otras subcategorías completas interesantes. Originalmente hice esta pregunta para subcategorías densas y el útil comentario de David Roberts más abajo muestra que no tendrás éxito aquí porque al ir al gráfico subyacente se pierden los datos de composición.

Otra pregunta de ejemplo, sobre productos de categorías:

2) El gráfico subyacente de $\mathcal{C}\times \mathcal{D}$ es el producto fuerte $G\boxtimes H$ de los dos gráficos subyacentes. ¿Existe una categoría correspondiente al producto cartesiano de dos grafos subyacentes? El producto tensorial (directo) ?

7voto

Ronnie Brown Puntos 7852

Existe una interacción entre la teoría de categorías y la teoría de grafos en

F.~W.~Lawvere. Distinciones cualitativas entre algunas topos de grafos generalizados. En { \em Categories in computer science and logic (Boulder, CO, 1987)/}, volumen~92 de { \em Contemp. Math./}, 261--299. Amer. Math. Soc., Providence, RI (1989).

que hemos explotado en

R. Brown, I. Morris, J. Shrimpton y C.D. Wensley, `Graphs of Morphisms of Graphs', Electronic Journal of Combinatorics, A1 of Volume 15(1), 2008. 1-28.

Pero en realidad se trata de posibles categorías de gráficos, que puede ser lo contrario de la pregunta que planteas.

Si nos fijamos en la teoría de los grupoides, los "grafos subyacentes" son fundamentales, por ejemplo para definir los grupoides libres. Véase, por ejemplo

Higgins, P.~J. Notes on categories and groupoids, Mathematical Studies, Volume~32. Van Nostrand Reinhold Co. Londres (1971); Reimpresiones en Theory and Applications of Categories, No. 7 (2005) pp 1-195.

Los grupoides son una especie de "teoría de grupos + grafos".

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