Definition talk:Graph (Graph Theory)

Refactor

Large but probably valuable project: turn this into a disambiguation page covering simple graphs, loop graphs, digraphs, loop digraphs, multigraphs, multidigraphs, pseudographs, pseudodigraphs, etc. A number of pages already seem to use this one as though it were something other than what it is. Vertices in Locally Finite Graph is clearly talking about some sort of multigraph/pseudograph, but just points here. Said theorem holds for simple graphs in such a trivial fashion as not to be worth mentioning, but as can be seen there it requires more work in other cases. --Dfeuer (talk) 19:44, 30 May 2013 (UTC)

Bad idea. --prime mover (talk) 20:08, 30 May 2013 (UTC)

Regardless of the possible merit such a page could have, I deem the graph theory section insufficiently populated to make this worthwhile presently. But we can keep the suggestion for later times. — Lord_Farin (talk) 21:44, 30 May 2013 (UTC)

As a graph theorist, I support this in principle. Maybe on one bored night I'll go through and actually go and refactor it and then try to cover some more basic results, as I did a long time ago. I recall a discussion about the best way to define a graph. Based on my work in algebra on graphs, the most general way is to define an edge set $E$, a vertex set $V$, an incidence relation on $V \times E$, and some way of labeling vertices, edges, and tentacles (a tentacle is a vertex-edge pair). Digraphs can be expressed via labeling tentacles.

My suggestion would be to attempt to present the most general definition possible, and then provide all the useful special cases. For instance, a simple undirected graph can be expressed as $\left(V, E\right)$ where $E \subseteq V$ and every edge has size 2. In this case, the incidence relation simply is $\in$. Every result should be as general as possible, perhaps with useful special cases mentioned where it's practical. As a perhaps-useful comparison, one of the most powerful results of the Graph Minors Project, of which the Graph Minor Theorem is a special case, is an expression about labeled hypgraphs. Scshunt (talk) 09:05, 5 August 2014 (UTC)

By $E \subseteq V$ in the above, don't you mean $E \subseteq V \times V$?

The formal definition that you suggest (except for the concept of tentacles which I haven't encountered before reading the above) has already been implemented in $\mathsf{Pr} \infty \mathsf{fWiki}$ in the various places as appropriate. It has been established that a graph / digraph / loop graph (but not multigraph) can be interpreted as a relation on the vertex set, and that a weighted graph (or network) can be interpreted (or modelled) as a mapping from a relation on the vertex set to a (usually) number set, and that a multigraph is a labelled graph where the codomain of the mapping is the set of integers.

I envisage this particular page as being a parent page which includes the "basic" definitions of the main graph types (simple graph, multigraph, loop graph, digraph and the various hybrids of these) as transclusions.

There is a danger, as we encountered with the page on Polynomials, of providing such a high level of abstraction at the outset, that the casual or non-specialist reader cannot penetrate the formal language of sets, relations and mappings when all they want is the practical aspect of vertices, edges and labels. Hence it is *essential* that we do not lose the definition of a graph in terms of "dots" and "lines", and only introduce the concept of a graph as a relation as a separate section once the intuitive, informal definition has been established. Like it's presented now, basically. --prime mover (talk) 12:23, 5 August 2014 (UTC)

(Yes, I meant $E \subset V \times V$) I agree that starting generally is a concern from a point of readability, and I'm a fan of writing pages in such a way as to avoid that. I think there's a way to write this that The issue with the current pages (as is, without any potential changes) is that the relations between classes of graphs are a mess, because of the attempt to name every single variant. I much prefer considering matters such as loops and multiple edges to be properties of the general graph, rather than separate definitions, because they're binary in nature. If we start with a simple graph, then we may have loops, may have multiple edges, may be a hypergraph, may be directed, may have edge labels, may have vertex labels, and that's 128 different definitions there, not counting tentacle labels (which are admittedly specialized) and other special cases (e.g. different types of labeled graphs, like vertex-coloured graphs or edge-coloured)

There's also already a fair amount of confusion among the various definitions about whether edges are properly viewed as subsets or ordered pairs. The definition of a graph inaccurately describes the two as being the same. Either definition may be useful in a given context, as can the view of a graph as an incidence structure between edges and vertices (this tends to be more useful when doing constructions). I feel like there's a good way to handle this but am not totally sure what it is.

In an undirected graph (which is what the word "graph" generally defaults to) an edge can be interpreted as a set (i.e. an unordered pair). In a directed graph (which this page does not define), an edge is an ordered pair. No problem. You can of course interpret an undirected graph as a directed graph where arcs come in pairs: one in one direction, one in the other. This is what is "really" meant when a graph is presented (and defined) as a (symmetric) relation on the set of vertices, I agree. But IMO it's counterproductive and an overcomplication to dismiss the definition of the edge of an undirected graph as a doubleton because then it obscures the basic simplicity of a graph's structure.

By all means (once the above refactoring has been done -- and please note the comment inside the "refactor" template) we can add a further definition of a "simple graph" whereby an edge is interpreted as a doubleton of ordered pairs, and then add a proof proving the equivalence of the definitions, but I would counsel against overcomplicating a simple concept just because it's clever to. --prime mover (talk) 18:49, 5 August 2014 (UTC)

Maybe when I'm not totally sleep-addled, I'll play around with something around my sandbox and then we can compare. It's possible I'm just in a phase of lunacy and the current way is best. Scshunt (talk) 12:50, 5 August 2014 (UTC)

First of all, thanks for taking the time to comment on this currently embryonic section of $\mathsf{Pr} \infty \mathsf{fWiki}$, which has not seen the delight of multiple passings-over to increase clarity, accuracy and simplicity of exposition. I will definitely keep a close eye to any developments in your sandbox, to see if they can assist in crafting graph theory into a useful addition to this site's repertoire.

Concerning the matter at hand, I think there is ample room for improvement regarding the formal definition section. It is fortunate that the informal definition keeps the exact relation between edges and vertices unspecified, so that we are at liberty to discuss multiple approaches towards a formal definition. One of the greatest challenges I think a thorough, non-idiosyncratic coverage of group theory sees itself confronted with is the fact that the very definition of graph is, well, non-existent; there are simply a lot of concepts that are being referred to as "graph".

It may therefore, in due time, be necessary to start separating out different (formal) definitions of graph, which we could then e.g. name after their most influential progenitors. However, to set up the graph theory section in such generality and with such diversity is likely to amount to a project many hundreds of man-hours in size. Perhaps we can see to it that such a project is split into clearly separated sub-projects, each with a clear, defined goal, which can then be assigned to, or taken up by, whoever is willing and capable to do so. (Which reminds me of several projects I have started that have been lying around for years now, inching forward towards completion every few months or so... But let us not digress.)

In light of the above, let me explicitly support your endeavours towards investigating different ways to formally define graphs, more so since you've actually worked in this area of mathematics.

Lastly, allow me to suggest that for the whole naming-and-shaming business this discussing originated from, we ought to simply use a format similar to Definition:Properties of Algebraic Structures of One Operation rather than making a half-hearted attempt to include some of them (in undoubtedly unsatisfying detail) as subpages of the master page Definition:Graph (Graph Theory). — Lord_Farin (talk) 15:12, 7 August 2014 (UTC)

Thanks for the comments. I did a simple sample version over at User:Scshunt/Definition:Graph. It is missing a lot of wiki style, but I was going for something quick. After working on that, I think that the ideal situation would be to define the most general incidence structure (as I discussed above) as something (call it a "graph-like structure"), and then carefully define everything else as special cases (though it's worth repeating the formal definition). This provides the greatest flexibility for moving between the various types of definition, and for having a common language which can be used when there is not a strong reason to do otherwise. We can then use a table like for algebraic operations to come up with exact names for the commonly-used concepts (although I'm torn what should be called a "graph", even conceptually: sometimes it means multigraph, sometimes it means simple graph, rarely it means loop-graph).

We also need a way to treat the equivalence of definitions. I can see at least three reasonable ways to go about it. The first is to formalize what we mean by equivalence using isomorphism (I'm not satisfied with [[1]] as is, not counting that it is missing 3 other proofs) and then ignore it in the general section of the wiki; we simply explain why a theorem about one definition of graph applies to another on the definition page, and then never speak of it again. This is easier, but runs the risk of accidentally relying on a detail of a definition not capture in its isomorphism properties. The second is to always start with a single definition, and then convert back and forth (e.g. "We may assume that $G = \left(V, E\right)$, defined with edges as sets").

Actually, as I write this, I'm increasingly thinking the answer might be to could go about this in a way more similar to how matroid theory is typically treated. We pick a concrete definition and then build the rest of the definitions around it. An example might be "The doubleton edge set a graph is the set $\left\{\left\{u, v\right\} \subseteq V : u \sim v\right\}$". We would then show that, given a set $E$ of two-element subsets of $V$, there is some unique (up to choice of edge set and permutation of edges) graph with the same vertex set such that $E$ is its doubleton edge set. This is slightly more verbose, but more flexible as it allows reference to the various definitions of a graph all at once.

Appreciate the work, and I see the direction you are taking it. However, I reiterate the desire for keeping the basic simplicity of the concepts. I still need to refactor the original page somewhat, putting the existing definitions into the currently standard style of multiply-defined concepts. I would also lose the language which comments on the relative quality of the definitions -- $\mathsf{Pr} \infty \mathsf{fWiki}$ style is deliberately sparse.

As may have been pointed out, this is an old page and was never properly styled into the current standard style (which evolved over the course of years) so it might be a good idea for it to be brought into line with the other pages. I have an idea of how this is to be done, I haven't done it because I'm just lazy. I will do, I promise. --prime mover (talk) 05:29, 13 August 2014 (UTC)

It occurs to me that if we go with the matroid-like approach, we can use the simpler definitions when convenient. So I'm thinking that I like this approach best of all. I will see about doing an alternate prototype before I try to remember how the style here works and/or learn the newer nuances to the style. Scshunt (talk) 07:29, 13 August 2014 (UTC)

As you see, I have refactored the page, splitting it into separate pages for the Formal and Informal definitions.

Two issues:

a) The formal definition comes in the 3 flavours that you have established, so the work you have done on this needs to go into the "Formal Definition" page (exactly how it is to be structured I haven't worked out yet).

b) The question of whether to separate out this definition into "Simple Graph" and make "Graph (Graph Theory)" a disambiguation and/or parent page is still not decided.

As to when I'll get round to thinking about it, I'm not sure. I suffer from lethargy. --prime mover (talk) 07:50, 13 August 2014 (UTC)