2
$\begingroup$

In conventional Graph Theory the role of Nodes and Edges is skewed: nodes are perfectly ok being aloof, but poor edges are always drawn between existing nodes (that is, the two maps from EDGES to NODES are total).

Now, I am curious to know if there is somewhere in the Mare Magnum of mathematics an extension of Graph Theory, let us call it provisionally the Theory Partial Graphs (it may have already a well-established name, in which case I apologize), which contemplates dangling edges (ie edges which either stand alone, or are attached only to one node).

To be more specific, I would like to see some refs on TYPED partial graphs: dangling edges hare equipped with types, and there is an algebra of sorts which tells which dangling nodes can "merge" with other kindred typed dangling nodes to make up a genuine edge of the graph

(think of nodes which protrude some edges like an octopus, with the possibility of two arms joining and forming a perfectly traditional edge).

Anything along the lines above?

PS Although I do not have any specific preconceptions around the way this theory may appear (for instance, as some kind of algebra, or as a chapter of topology), ideally it would be codes within a categorical framework

$\endgroup$
  • 2
    $\begingroup$ Do you really expect something drastically new out of such a theory? What about assigning types to monovalent edges (one of which being the type "missing")? Or, personally, I studies dessins d'enfants with all white vertices $1$- or $2$-valent, and tried to erase such vertices by introducing solid and hanging edges. But I gave up as I saw no advantages in this approach. $\endgroup$ – Alex Degtyarev Feb 21 '14 at 16:59
  • $\begingroup$ Dear Alex, let me tell you the truth (albeit partial truth). This question of mine is motivated by data modeling, I have something very precise in mind which requires a few ingredients, one being these partial graphs. Now, if there is nothing there already, I can of course try to develop the math and then move to my real end, but I have learned both as a mathematician and as a data modeler that it is always a bad idea to re-invent the wheel, hence my question. If you have thought of something already, do elaborate. I am curious as to which path led you there $\endgroup$ – Mirco A. Mannucci Feb 21 '14 at 17:03
  • 2
    $\begingroup$ This sounds like a fishing expedition. What questions about "standard" graphs are you hoping to generalize and answer? What sort of results are you looking for? You allude to some sort of dynamics regarding partial edges joining -- can you elaborate on this? $\endgroup$ – Noah Stein Feb 21 '14 at 17:42
  • $\begingroup$ LOL! Believe it or not, you are on the right track, but allow me to keep a little secret here. What I can share has been already caught by your savvy comment: yes, I am after some kind of dynamics of graphs, say evolving graphs in which nodes attempts to find matches, by spawning "sensor-edges". These edges carry some qualifier, a type, and matches (ie real edge generation) happens only for the right sensor-edges types (at a more sophisticated level, one could assign probabilities of matching, thereby having a new theory of random graphs growth) $\endgroup$ – Mirco A. Mannucci Feb 21 '14 at 17:49
  • 1
    $\begingroup$ If I understand correctly, Feynman diagrams (e. g., §III.2 of Dominique Manchon's arXiv:0408405v2) are graphs like you want, Mirco. I've never fully understood their definition, which is perhaps unsurprising for a notion that mostly physicists care about. If you want to know more, papers by Alessandra Frabetti and Kurusch Ebrahimi-Fard might be a good place to start. $\endgroup$ – darij grinberg Feb 22 '14 at 21:25
6
$\begingroup$

Yes, there are such things.

Consider the monoid $M$ of endomaps $\{0,1\} \to \{0,1\}$. It has four elements: the constant maps 0 and 1, the identity map $i$ and the "swap" map $s$. Let $\mathcal{G}$ be the category of right $M$-actions. These are sets equipped with a map $m : A \times M \to A$ such that $m(x, i) = x$ and $m(x, f \circ g) = m(m(x, f), g)$. A morphism is a map which commutes with the actions. I will write $x \cdot f$ instead of $m(x, f)$. (All this is very common, except that we have a monoid instead of a group.)

Let us think of the elements of an $M$-set $A$ as half-edges. Each half-edge $e \in A$ has an associated opposite half-edge $e \cdot s$. Call a half-edge $e$ a vertex when $e \cdot 0 = e$ (exercise: $e \cdot 0 = e \iff e \cdot 1 = e$). Each half-edge $e$ has an origin which is $e \cdot 0$, while $e \cdot 1$ is the origin of its opposite half-edge $e \cdot s$. It is possible to have a half-edge which is its own opposite, $e \cdot s = e$ (these are your dangling edges). The graphs are reflexive because every vertex $v$ has a distinguished half-edge attached to it, namely $v$ itself.

Explicitly, we have the following equivalent presentation of $\mathcal{G}$:

  1. objects are sets $(V, H)$ of vertices and half edges such that:

    • each half-edge $e \in H$ has an origin $o(e) \in V$
    • each half-edge $e$ has an opposite half-edge $s(e) \in E$
    • each vertex $v \in V$ has a distinguished half-edge $\ell(v) \in H$ such that $o(\ell(v)) = v$ and $s(\ell(v)) = \ell(v)$
  2. A morphism $(V,H) \to (V',H')$ is a pair of maps $f : V \to V'$ and $g : H \to H'$ such that $g(\ell(v)) = \ell(f(v))$, $f(o(e)) = o(g(e))$, and $s(g(e)) = g(s(e))$. Morphisms are composed component-wise.

This an more can be read about in:

William F. Lawvere, Qualitative distinctions between some toposes of generalized graph, Contemporary mathematics, Vol. 92, 1989, pp. 261-299.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great! Thanks Andrej. Do you happen to know if Lawvere's initial setup has developed into some organic theory of generalized graphs? Also, I will read the original paper, of course, but do you have an idea as to what was his original motivation? Thanks again, your answers are always most welcome $\endgroup$ – Mirco A. Mannucci Feb 21 '14 at 19:09
  • $\begingroup$ I don't know about Lawvere's motivation. As far as I know, not too much has been persued in this direction. There are however other group actions on sets that correspond to various kinds of graphs. $\endgroup$ – Andrej Bauer Feb 21 '14 at 20:07
3
$\begingroup$

The theory of signed graphs might be helpful. Although they were conceived in the social sciences (hey, how many math concepts do you know that can claim that...?), they are can be viewed as a type-B analogue of graphs (in the representation-theoretic sense), and as such half edges appear quite natural. (They can also have loose edges, which have no endpoint. That's arguably a bit weird, but again, it fits naturally into the theory.) If this sounds remotely interesting, start with Zaslavsky's excellent survey article or his annotated bibliography.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great Ref!!! Thanks Matthias, very very helpful.... $\endgroup$ – Mirco A. Mannucci Feb 21 '14 at 22:58
3
$\begingroup$

Once you are in the setting where vertices have types (which usually would be called "colours" in the graph literature), there is little point in having edges with missing endpoints - just use introduce a new colour for vertices that are "not really there" (and if you want to distinguish different kinds of edges, give the virtual vertices different colours).

Now the situation that vertices in a graph are identified according to some rules seems to be pretty common occurrance. E.g. a simple system of the kind you are interested in could be described in the following way using a more typical graph theory language:

Let G, H be a graph where the vertices are coloured red, green and white. Write $G \preceq H$ if there are two vertices $v, u$ in $H$ such that $v$ is coloured red, $u$ is coloured green and that $G$ is obtained from $H$ by identifying $v$ and $u$ and colouring the resulting vertex white.

Question: Given some particular coloured graph $H$, what are the graphs $G \preceq H$ coloured completely white?

I'm not aware of any good overview on such approaches, but hopefully such a reformulation can help you finding the kind of results you are looking for.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hmmmm, I just gave you my point fro your answer (gotta start somewhere), but I have my reservations on your proposals: you are modeling some "data structure" where the nodes carry the type, but what I am after is instead a edge type. They are not the same thing: nodes may perhaps be "the same thing" (ie have the same universal type, but they may protrude different types of edges (think of those edges as sensors). Depending on the edge type they have protruded, they may match or may not. This is the scenario I have in mind.... $\endgroup$ – Mirco A. Mannucci Feb 21 '14 at 17:21
  • 1
    $\begingroup$ Probably, this discussion is meaningless unless we know what you need. In my opinion, a graph is a certain combinatorial structure that can be studied by means of geometric intuition: this is the power of the approach. One can change the combinatorics any way one likes, but then there's no need to call it a graph :) Back to the scarce hints you've given, for you an edge is a pair of pointers. Then, just say that one or both of them may be $\mathrm{nil}$. The closest mathematical analogy seems introducing a dummy vertex (at address $0$) and attaching all hanging edges to it. $\endgroup$ – Alex Degtyarev Feb 21 '14 at 18:02
  • 1
    $\begingroup$ I've edited my answer to clarify. Whatever type a "halfedge" would carry can be attached to the "virtual" vertex you are inserting to complete it. Only if "completed edges" still need to carry different types it becomes more complicated. $\endgroup$ – Arno Feb 21 '14 at 22:10
  • $\begingroup$ Your suggestion is simple but perhaps promising: one "completes" the graph adding the generic node, say N0. Even with types one can handle the extra-complexity: for instance by saying this: if first edge from node N1 has type T1 and second edge from node N2 has type T2 and T1 is compatible with T2, we close the triangle (N1, N0, N2) by adding a real edge from N1 to N2. Good material for thought... $\endgroup$ – Mirco A. Mannucci Feb 21 '14 at 23:27
0
$\begingroup$

There exist partial algebras ( having nontotal basic operations ), multi-typed structures, hypergraphs, and various flavors of categories, so why not partial multigraphs?

Unfortunately, your description is too brief for me to provide specific references. You may want some version of multi-typed clone or n-category variant. Also, you should come up with a sound reason for why you want a dangling edge instead of a terminated edge. (Electrical engineers do it for safety, so should data scientists.)

I recommend talking to yourself more about what you want to do with these objects, and then hit the data modeling literature or perhaps those texts applying categories to computer science. Waiting a couple days and then asking a better version on data or CS forums wouldn't hurt, not much anyway.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Dear "masked avenger", who tells you that I have not "talked to myself more about what I want"? I know EXACTLY what I want. And, I happen to know something of all of the above, but so far I have not found what I am looking for (hence reaching out to mathoverflow). I would be more than happy to find out that the theory of dangling edges has been fully worked out somewhere, so that I can use it for my own agenda. If this turns out not to be the case, well, I will write it down myself. $\endgroup$ – Mirco A. Mannucci Feb 21 '14 at 18:36
  • 1
    $\begingroup$ Dearest Mirco, you did, by using the phrase "not having any specific preconceptions" in your post. I suspect your comments tell a different story, but just based on your post I formed a recommendation and gave it. You have in my opinion the beginning of a good question, but for this forum not a GOOD question. I hope you get good answers nonetheless. If I find I can improve my answer, I will. $\endgroup$ – The Masked Avenger Feb 21 '14 at 18:55
  • $\begingroup$ Ok,sounds good.I respect your opinion, maybe I will reshape my question, you may have a real point. But, on the other hand, I cannot and will not share my motivations, more than I have already done already. This is a math forum, actually the best in the planet, but not a place to say: -hei I am working at this wondrous theory, will you please publish it for me? - What I can do, is flesh it out more from a math standpoint...PS I am open to criticism, but just remember one thing: two years ago I posted a question which a moderator wanted to remove, it turned out to be a 7K views one... $\endgroup$ – Mirco A. Mannucci Feb 21 '14 at 19:01
  • 1
    $\begingroup$ No offense intended or taken. Also it is possible for me to misread your question despite your best efforts. Hopefully my opinion helps and/or inspires; the only guarantee I give is that it is an opinion of mine. Good luck. $\endgroup$ – The Masked Avenger Feb 21 '14 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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