3
votes
0answers
33 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
0
votes
0answers
23 views

example of algebraic theory,free product completion,graphs

Let us denote by $\def\Graph{{\sf Graph}}\Graph$ the category of directed graphs $G$ with multiple edges: they are given by a set $G_v$ of vertices, a set $G_e$ of edges, and two functions from $G_e$ ...
4
votes
1answer
107 views

Category theory for graph theory research

I am doing research in algebraic graph theory, focusing on the relation between graphs and groups (especially the representing groups as graphs) for my Ph.D. In particular, one of the ideas is to ...
1
vote
1answer
61 views

Showing that a diagram commutes in the most economical way

Suppose that one had to consider (co)cones on a complicated diagram, with many arrows and objects and that one wished to prove that one of them is final/initial. Given another (co)cone, one would ...
3
votes
2answers
96 views

Right adjoint to forgetful functor $\mathbf{Cat} \to \mathbf{Graph}$

There is a forgetful functor $U:\mathbf{Cat} \to \mathbf{Graph}$, which assigns a (small) category to its underlying (small) graph. Also, it has a left adjoint $F:\mathbf{Graph} \to \mathbf{Cat}$, ...
0
votes
0answers
28 views

An interleaved path of arrows in a category/digraph

In what I am doing now, a slightly strange concept emerged; My objects are sequences of arrows $\{f_i\}_{i=1}^{n}$ in a small category such that for every $1\leq i\leq n-1$, there is an arrow from the ...
0
votes
0answers
13 views

What's the name for the union of a set of any graph and the set of its related hypergraphs?

So any graph can, if you arbitrarily partition the vertices into two groups represent, in that bipartite form, the incidence graph of a corresponding hypergraph. Is there anything special or known ...
0
votes
2answers
126 views

Category theory - where is my error?

In Explicit formula for exponential objects in category of digraphs and its answer we have currying/uncurrying (which I will denote $\sim$ and $-$) as exponential transpose for the category ...
1
vote
1answer
144 views

Explicit formula for exponential objects in category of digraphs

I have already asked a similar question: Exponential object in a category of graphs but earlier I have asked only about existence of exponential object, while in this question I ask for exact formulas ...
5
votes
2answers
165 views

Pullbacks and pushouts in the category of digraphs?

By definition the category of digraphs is: Objects are endomorphisms of the category $\mathbf{Rel}$ (that is sets equipped with a binary relation on that set). Morphisms from an object $\mu$ to an ...
2
votes
2answers
58 views

Generalizations of colorability

It is fun to recognize that the $n$-colorable graphs are exactly those graphs $X$ in the category of simple graphs with an homomorphism to the complete graph $K_n$. Question 1: Are there other ...
1
vote
0answers
50 views

What are co-products for directed graphs?

I define a digraph as a set $V$ (vertexes) and a relation $E$ (edges) on $V$. Morphisms of digraph are functions which preserve $E$. So we have a category. What are co-products in this category? (I ...
3
votes
1answer
110 views

Categorical characterization of complete graphs

In the category of (finite) simple graphs with graph homomorphisms $\mathsf{SimpGph}$, (how) can the complete graphs $K_n$ be characterized by genuinely categorical means? Are they somehow ...
4
votes
2answers
106 views

Is there an algorithm for determining when two graphs are isomorphic?

The title says it all. Is there such an algorithm? More generally, is there an algorithm for deciding when two objects are isomorphic in a particular category?
1
vote
1answer
63 views

Systematizing graph morphisms

Trying to systematize possible notions of graph morphisms I came about the following classification: A morphism $f$ which sends a graph $G$ to another graph $G'$ is – first of all – ...
1
vote
0answers
35 views

Possible number of endofunctors

The discrete category with countably many objects and morphisms has uncountably many endofunctors (= the number of functions from $\mathbb{N}$ to $\mathbb{N}$). Which categories with countably many ...
8
votes
1answer
255 views

What distinguishes topological spaces from graphs?

Topology would not "work" if one reverted the "direction" in the definition of continuous maps $f$: $$\text{open}(x) \rightarrow \text{open}(f(x))$$ It has to be $$\text{open}(f(x)) \rightarrow ...
7
votes
1answer
105 views

Universal properties of “interesting” families of graphs

Can cycles – and/or other "interesting" families of graphs like paths, trees, hypercubes, etc. – be characterized by a universal property in the category of graphs? I admit that there is ...
2
votes
1answer
74 views

Are concepts and properties studied in a category all preserved by morphisms?

When study a category, are we only interested in those concepts and properties preserved by the morphisms, not those which cannot be preserved? For example, in Terry Tao's blog We say that one ...
3
votes
1answer
244 views

The opposite category of the category of graphs

Does anyone know where I can find a description of the opposite category of the category of graphs? The morphisms of the category are graph homomorphisms. Thank you
1
vote
2answers
86 views

Why don't all transitive graphs with a single loop define a category?

I'm reading Abstract & Concrete Categories: The Joy of Cats. On exercise 3A(c), the author defines the graph of a category C to be the large graph whose vertices are the objects in C, and whose ...
2
votes
2answers
118 views

Which graph products are categorical products?

There is a whole bunch of definitions of graph products, but only one of them - the tensor product - is the categorical product in the (standard) category of graphs with graph homomorphisms. I'd ...
1
vote
1answer
132 views

Right adjoint to forgetful functor from “dynamical system” digraph

Question about "dynamical systems," as Lawvere/Schnauel calls them in their baby book (ie digraph w exactly 1 arrow out of each point). What would a "chaotic" dynamical system be? In the book's ...
5
votes
0answers
97 views

What is special about simplices, circles, paths and cubes?

There are some ubiquitous families of graphs — the complete graphs (or simplices) $K_n$, the circle graphs $C_n$, the path graphs $P_n$, and the hypercube graphs $Q_n$ — that intuitively ...
1
vote
1answer
232 views

Do the terms “quiver” and “meta graph” refer to the same concept?

Do the terms "quiver" and "metagraph" refer to the same concept? Or is there a distinction I am missing. My sources are Quiver - http://ncatlab.org/nlab/show/quiver Metagraph - ...
0
votes
2answers
225 views

Category of Trees as sub-category of Category of Graphs

A tree (like a binary search tree) is a direct graph with some limitations (no cycles, connected). How can I express the category of trees as "sub-category" of a graphs? There is a way? I'm not sure ...
13
votes
0answers
265 views

Is Erdős' lemma on intersection graphs a special case of Yoneda's lemma?

Under which name is the following proposition filed actually: Every poset $P$ embeds fully and faithfully in the powerset of $P$, ordered by subset inclusion. Let me call it Dedekind's lemma. ...
2
votes
1answer
45 views

Reducts of categories

There are several ways to reduce a category. The skeleton of a category is the category with isomorphic objects collapsed into one i.e. the only isomorphisms that remain are the identities. What's ...
3
votes
1answer
141 views

Looking for a review of the book Monoids, Acts and Categories

I have been looking for a review of the following book: Monoids, Acts and Categories with Applications to Wreath Products and Graphs by Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev but i was ...
-3
votes
1answer
102 views

Labeled and unlabeled categories

When one talks about the category $V_K$ of vector spaces over a field $K$ and considers the dual functor $D$ which maps a vector space $V$ to its dual $V^{*}$ I believe to have in mind something like ...