It's common to describe the category of (directed, multi-) graphs as a functor category Graph := [2, Set], where 2 here is the category with 2 objects and 2 parallel arrows (s & t). For a pair of sets (V,E), one can construct the indiscrete graph I(V,E) as a graph with vertices V and edges E x V x V, where the source and target maps are just the 2nd and 3rd projection respectively. This gives a right adjoint to the forgetful functor from Graph to pairs of sets. This enables one to construct a category of graphs with a fixed set of vetex/edge labels as a slice over Graph: Graph / I(Lv, Le) since a graph hm G --> I(Lv,Le) is the same as a map U(G) --> (Lv,Le), which is just a pair of functions assigning labels to the vertices and edges of G. This seems to me like a pretty standard trick, which extends to any functor category from a C which is in some sense "suitably acyclic". For instance, consider a category of "partitioned graphs" [3, Set], where 3 has objects (P,V,E) and arrows: E --s--> V, E --t--> V, and V --p--> P where, p assigns each of the vertices a partition. For a triple (P,V,E) we can form the indiscrete partitioned graph with: - partitions P - vertices V x P - edges E x (V x P) x (V x P) - p = pi2, s = pi2, t = pi3 which gives a right-adjoint to the forgetful functor from partitioned graphs to triples of sets. This is clearly an instance of a general recipe, whereby you start with the objects with no arrows out, and work your way backwards, always adding copies of the codomain of every out-arrow. Again one can attach labels to partitioned graphs by slicing: [3,Set] / I(Lp,Lv,Le) So, my question: Is the general case a known/studied construction? If so, could someone provide a reference? Best, Aleks [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Yes, indiscrete isn't exactly right. Perhaps something like "saturated" is more appropriate. Right Kan extensions give a nice way to put this, which makes it clear that this extends beyond finite base category as well. So, the refinement of my question is: have people studied (left or) right Kan extensions over the inclusion into C of its associated discrete category C0? It seems to me for instance that taking C = the simplicial category and C0 = natural numbers would have been studied, e.g. in forming something like "coloured simplicial sets" as a slice. On 20 December 2015 at 03:28, Steve Lack <steve.lack@mq.edu.au> wrote:
Dear Aleks,
I would say that the known construction of which this is a special case is right Kan extensions. The forgetful functor from graphs to pairs of sets is given by restriction along the inclusion in what you call 2 of the subcategory with the same object but no non-identity arrows. Thus the right adjoint is given by right Kan extension along this inclusion. Such right Kan extensions can always be constructed using limits; in your case, because the domain of the functor along which you are extending is discrete, these limits are actually products.
By the way, I would not use “indiscrete” in this context. For me indiscrete would refer to things in the image of the right adjoint to the functor which associates to a graph its set of vertices. The set of edges of the indiscrete graph would then be V x V.
Regards,
Steve Lack.
On 19 Dec 2015, at 9:48 PM, Aleks Kissinger <aleks0@gmail.com> wrote:
It's common to describe the category of (directed, multi-) graphs as a functor category Graph := [2, Set], where 2 here is the category with 2 objects and 2 parallel arrows (s & t).
For a pair of sets (V,E), one can construct the indiscrete graph I(V,E) as a graph with vertices V and edges E x V x V, where the source and target maps are just the 2nd and 3rd projection respectively. This gives a right adjoint to the forgetful functor from Graph to pairs of sets. This enables one to construct a category of graphs with a fixed set of vetex/edge labels as a slice over Graph:
Graph / I(Lv, Le)
since a graph hm G --> I(Lv,Le) is the same as a map U(G) --> (Lv,Le), which is just a pair of functions assigning labels to the vertices and edges of G.
This seems to me like a pretty standard trick, which extends to any functor category from a C which is in some sense "suitably acyclic". For instance, consider a category of "partitioned graphs" [3, Set], where 3 has objects (P,V,E) and arrows:
E --s--> V, E --t--> V, and V --p--> P
where, p assigns each of the vertices a partition. For a triple (P,V,E) we can form the indiscrete partitioned graph with:
- partitions P - vertices V x P - edges E x (V x P) x (V x P) - p = pi2, s = pi2, t = pi3
which gives a right-adjoint to the forgetful functor from partitioned graphs to triples of sets. This is clearly an instance of a general recipe, whereby you start with the objects with no arrows out, and work your way backwards, always adding copies of the codomain of every out-arrow. Again one can attach labels to partitioned graphs by slicing:
[3,Set] / I(Lp,Lv,Le)
So, my question: Is the general case a known/studied construction? If so, could someone provide a reference?
Best,
Aleks
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
The forgetful functor [C,Set] --> Set/ob C always has a right adjoint, given by right Kan extension along the inclusion C_0 --> C, where C_0 is the discrete category with the same objects as C. For the same construction in a more general context, see B2.3.16 in `Sketches of an Elephant'. Peter Johnstone On Sat, 19 Dec 2015, Aleks Kissinger wrote:
It's common to describe the category of (directed, multi-) graphs as a functor category Graph := [2, Set], where 2 here is the category with 2 objects and 2 parallel arrows (s & t).
For a pair of sets (V,E), one can construct the indiscrete graph I(V,E) as a graph with vertices V and edges E x V x V, where the source and target maps are just the 2nd and 3rd projection respectively. This gives a right adjoint to the forgetful functor from Graph to pairs of sets. This enables one to construct a category of graphs with a fixed set of vetex/edge labels as a slice over Graph:
Graph / I(Lv, Le)
since a graph hm G --> I(Lv,Le) is the same as a map U(G) --> (Lv,Le), which is just a pair of functions assigning labels to the vertices and edges of G.
This seems to me like a pretty standard trick, which extends to any functor category from a C which is in some sense "suitably acyclic". For instance, consider a category of "partitioned graphs" [3, Set], where 3 has objects (P,V,E) and arrows:
E --s--> V, E --t--> V, and V --p--> P
where, p assigns each of the vertices a partition. For a triple (P,V,E) we can form the indiscrete partitioned graph with:
- partitions P - vertices V x P - edges E x (V x P) x (V x P) - p = pi2, s = pi2, t = pi3
which gives a right-adjoint to the forgetful functor from partitioned graphs to triples of sets. This is clearly an instance of a general recipe, whereby you start with the objects with no arrows out, and work your way backwards, always adding copies of the codomain of every out-arrow. Again one can attach labels to partitioned graphs by slicing:
[3,Set] / I(Lp,Lv,Le)
So, my question: Is the general case a known/studied construction? If so, could someone provide a reference?
Best,
Aleks
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
participants (2)
-
Aleks Kissinger -
Peter Johnstone