Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf sheaves simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

Atrium > Mathematics, Physics & Philosophy: Category of Graphs

Bottom of Page

1 to 6 of 6

  1.  
    • CommentRowNumber1.
    • CommentAuthorMrBean
    • CommentTimeJan 26th 2016
    • (edited Jan 26th 2016)
    Colleagues!
    I need some help!

    I can't understand, what is exponential object in the category of graphs. I've already read some articles about this problem, but I'm trying to recognize the kind of logic, by which we can build this object.
    Thank you.
    • CommentRowNumber2.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 26th 2016

    Depends what you mean by “graph”, and morphisms of graphs. If you mean what category theorists usually mean, aka a quiver, then since that category is a presheaf category, exponentials are given by a well-known formula where Y X(c)=hom(X×hom(−,c),Y)Y^X(c) = \hom(X \times \hom(-, c), Y).

    I’m not sure that all the usual notions of graph and morphisms thereof do have exponentials, but some of them are quasitoposes, for example what I called the category of simple graphs. In the case of simple graphs, which are equivalent to presheaves GG on the category of finite sets 1,21, 2 (of those cardinalities) and functions between them such that the source target pairing

    • ⟨F(i 0),F(i 1)⟩:F(1)→F(0)×F(0)\langle F(i_0), F(i_1) \rangle: F(1) \to F(0) \times F(0)

    is monic, it turns out that this is the category of ¬¬\neg \neg-separated presheaves, and so you’d form exponentials as you do in the presheaf category.

    But anyway, you should tell us exactly which category of graphs you have in mind (objects and morphisms).

    • CommentRowNumber3.
    • CommentAuthorMrBean
    • CommentTimeJan 26th 2016
    Thank you for fast answering!

    I mean the formal definition of graph (G = (V, E)) in combinatorics and their homomorpishms as morphisms in category.
    • CommentRowNumber4.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 26th 2016

    No: please write out exactly what you mean. I’m not going to try to guess.

    • CommentRowNumber5.
    • CommentAuthorMrBean
    • CommentTimeJan 26th 2016
    Suppose, G = (V, E); G' = (V', E'), V is a vertex set, E is a edge set.
    Morphism (exactly what I mean) is a map from the first one vertex set to the second one: f:V(G) → V(G'), where (f(v_i), f(v_k)) ∈ E'(G') if (v_i, v_k) ∈ E(G).
    For example, Pierce "Category theory for computer scientists", P. 51:
    Pierce talks about category of directed multigraphs what the morphism definition as graph homomorphism.

    Sorry for my slowing-down.
    • CommentRowNumber6.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 26th 2016
    • (edited Jan 26th 2016)

    Sigh. As I said in #2, there are various notions of graph, and you still haven’t said which one you mean, exactly. Here is a questionnaire:

    Are you allowing multiple edges between a given pair of vertices?

    Are your graphs directed (i.e. are the edges directed)?

    Are you allowing vertices to have loops at them? Must there be a loop at every vertex?

    I don’t have Peirce’s book, so this is no help (and he may talk about the category of directed multigraphs, but is that exactly the notion you want, in which case I already answered, or are you working with a different notion?). Notions of morphism may also be subtly different, depending on what you want exactly.

    Possibly your question was addressed here or here.

1 to 6 of 6

  1.