Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In the category $\mathsf{Graph}$ of simple graphs with graph homomorphisms we'll find the following situation (the big circles indicating objects, labelled by the graphs they enclose, arrows indicating the existence of a homomorphism):

enter image description here

Speaking informally, the "obvious" structural relatedness between the two circle graphs $C_3$ and $C_4$ reduces to its two common subgraphs $P_3$ and $P_4$, with $P_3$ being a subgraph of $P_4$.

But even though there is an "undeniable" structural relatedness between $C_3$ and $C_4$, there is no single graph homomorphism between the two. This in complete contrast to the category $\mathsf{Top}$, where they are even isomorphic. (Instead of this: no arrows between $P_i$ and $C_j$!)

But why is there no graph homomorphism between $C_3$ and $C_4$? There are two interrelated reasons:

  1. If all vertices of a graph were forced to have a self-loop, there would be a homomorphism from $C_4$ to $C_3$, since two adjacent vertices $x,y$ were allowed to be mapped onto the same vertex $f(x)=f(y)$. Furthermore, there would also be a homomorphism from $P_4$ to $P_3$.

  2. If one insists on graphs to be loop-less (as in topological graph theory?), one might instead weaken the definition of a graph homomorphism. Instead of defining $f:G\rightarrow G'$ to be a homomorphism when $(x,y) \in E(G)$ implies $(f(x),f(y)) \in E(G')$, one might define it like this:

    $f:G\rightarrow G'$ is a (weak) homomorphism when $(x,y) \in E(G)$ implies $f(x) = f(y) \vee (f(x),f(y)) \in E(G')$.

My questions are:

  1. In which contexts does this definition of a (weak) homomorphism between simple graphs have drawbacks other than not being standard, e.g. technical ones?

  2. Is there a known or imaginable "problem" that might be easier to handle with weak homomorphisms (other than the missing homomorphism between $C_4$ and $C_3$ which isn't really a problem)?

  3. Might weak homomorphisms be conceptually more appropriate, i.e. catch the "meaning" of structure preserving better?

  4. Where can I find weak homomorphisms in the literature, maybe under another name?

share|improve this question
3  
I would guess that one reason for the emphasis on the existing definition is that it is convenient for graph coloring problems, since a coloring of $G$ with $r$ colors is a graph homomorphism from $G$ to $K_r$. But I've only been watching this area from afar, e.g. the development of topological lower bounds on chromatic numbers. –  Patricia Hersh Nov 11 '12 at 22:48
3  
Isn't it true that anything you can do with weak homomorphisms could be done by first adding loops everywhere then using usual homomorphisms? If so, I don't see what is gained. (Btw, topological graph theorists allow loops sometimes; even maps with a single vertex and lots of loops are interesting.) –  Brendan McKay Nov 11 '12 at 23:32
3  
Might be conceptually more appropriate for what, drawbacks when trying to do what ? Definitions do not exit in the vacuum; they are worth their usefulness in gold. What are you trying to achieve? –  Mariano Suárez-Alvarez Nov 12 '12 at 5:14
2  
[@Mariano] I'd like to know in which contexts and for what specific reasons the stronger notion of graph homomorphism is more useful - and thus successful - than the weaker. Patricia in her comment gave such a perfect reason. –  Hans Stricker Nov 12 '12 at 8:17
3  
My point is that one does not usually come up with a more or less random definition and then ask people around what it is good for and why others use another. You say that something is obvious and that something else is undeniable: but why do you want there to be a morphism between the graphs where there isn't? That someone somewhere has preferred the well-known definition of morphism is worth-knowing, but a motivation for your question would not be bad, either! –  Mariano Suárez-Alvarez Nov 12 '12 at 16:12
show 3 more comments

2 Answers

What you are describing is sometimes goes under the phrase reflexive vs. irreflexive graphs. What you seem to be describing are two categories:

  • Irreflexive graphs: the objects are sets with irreflexive symmetric relations, the morphisms are relation-preserving functions on the underlying sets.

  • Reflexive graphs: the objects are sets with reflexive symmetric relations, the morphisms are relation-preserving functions on the underlying sets.

It is fun to compute cartesian products in both of these and to discover the two well-known kinds of graph products. Graph theorists could benefit from a bit of category theory.

There are actually many variations on categories of graphs. Here are some others.

Graphs as relations

The categories of relations and relation-preserving functions are categories of simple graphs. We can require various additional properties. Symmetric relations give us symmetric graphs, reflexive relations give us graphs in which morphisms are allowed to squish edges, etc.

Directed graphs

This is perhaps the most straightforward example. Let $\mathcal{C}$ be the category with two objects, called $\mathsf{E}$ and $\mathsf{V}$ and two arrows $\mathsf{s}, \mathsf{t} : \mathsf{E} \to \mathsf{V}$. Then the (covariant) presheaf category $\mathbf{Set}^\mathcal{C}$ is just the category of directed graphs. An object of the category can be viewed as a pair of sets $(E, V)$ together with two maps $s, t : E \to V$.

Reflexive directed graphs

We can play with directed graphs. For example, if we add an arrow $\mathsf{r} : \mathsf{V} \to \mathsf{E}$ which is a common right inverse of $\mathsf{s}$ and $\mathsf{t}$, we obtain directed graphs with chosen loops.

Symmetric graphs

Another option is to add an arrow $\mathsf{o} : \mathsf{E} \to \mathsf{E}$ satisfying $\mathsf{t} \circ \mathsf{o} = \mathsf{s}$ and $\mathsf{o} \circ \mathsf{o} = \mathsf{o}$ (yes, I am using different kinds of circles on purposes to confuse you). The presheaf category then corresponds to directed graphs in which each edge $e : a \to b$ has an opposite $o(e) : b \to a$, and "opposite" is an involution. It may happen that a loop is its own opposite.

Graphs as monoid actions

To get more fun out of categories of graphs we can do the following. Let $M$ be the monoid of functions $\lbrace 0, 1 \rbrace \to \lbrace 0, 1 \rbrace$. There are four elements, the identity $1$, the map $t$ which swaps $0$ and $1$, and the two constant maps $0$ and $1$. The category of right $M$-actions can be seen as a category of graphs.

Suppose $(X, m : X \times M \to X)$ is a right action on $X$. This is a graph in the following sense. The vertices are those elements of $X$ that are fixed by the action of $0$, or equivalently by the action of $1$. We do not have edges, but rather "half-edges". A half-edge is an element of $X$ which is not a vertex. Each half edge $e$ has its mate $e \cdot t$, and together you can think of them as a wholesome edge (unordered). A half-edge $e$ is attached to the vertex $e \cdot 0$, while its mate is attached to $e \cdot 1$.

We almost get the usual symmetric (non-simple) graphs, except that there can be degenerate half-edges that are their own mates (and therefore necessarily loop-like).

The relevant reference for this answer is Bill Lawvere's Categories of spaces may not be generalized spaces as exemplified by directed graphs.

share|improve this answer
add comment

What you call a weak homomorphism is just a simplicial map where we view graphs as 1-dimensional simplicial complexes. In my opinion these are very natural and important outside of the coloring context. Here are my reasons:

  1. The endomorphism monoid is much richer if you allow simplicial maps. The endomorphism of the complete graph are only automorphisms under the rigid definition. Using simplicial maps it is all maps on the vertices.

  2. You cannot contract a spanning tree with the rigid definition.

  3. I defined orbital graphs for transformation monoids to generalize D. Higman's theorem but the monoid must be allowed to crush edges for it to work.

Adding loops is not a good solution in my opinion because it changes the fundamental group and homology. For instance, if a monoid acts on a graph by simplicial maps, then the chain groups become modules. Adding loops gives the wrong effect since crushing an edge should give the zero map.

share|improve this answer
    
I have a problem with statement 2 .If you are calling the rigid definition that for homomorphism of graphs which is classical . Then you can contract any tree to K_2 (the complete graph with 2 vertices). –  Jérôme JEAN-CHARLES Dec 24 '13 at 17:27
    
I mean contract a spanning tree inside a bigger graph not contract a tree. I also mean to a single vertex not K_2. –  Benjamin Steinberg Dec 24 '13 at 20:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.