Talk:Hypergraph

Notation

This article needs the notation unifying between what I've just added and the rest. Rich Farmbrough 20:54, 26 August 2005 (UTC)

Set of Subsets

Someone not logged in just changed S(X) (as the set of subsets of X) to P(X). I'll consider it as a vandalism (specially because he or she didn't log in), but there's a reason for the exchange? --FernandoAires 11:54, 22 August 2006 (UTC)

A script P ("P" for "power set") is commonly used to denote the collection of all subsets of a set. Austinmohr (talk) 19:19, 9 May 2011 (UTC)

Image

I would just like to point out that the graph depicted on the page is not really a hypergraph. Since node 7 is not a part of any edge, but is in the nodeset of the graph, taking the dual will lead to an empty edge, not allowed according to the definition. I think also that Berge stated in his book that the superunion of the edges should be equal to the nodeset. /Jonatan —Preceding unsigned comment added by 130.243.173.106 (talk) 17:52, August 30, 2007 (UTC)

Yep, sounds right. linas (talk) 17:30, 24 July 2008 (UTC)

It is correct that Berge would have disallowed it. Quite a lot of hypergraph theorists would allow, though. There is actually another reason it doesn't have a dual: vertices v5 and v6 would map to equal edges while the definition on this page only allows distinct edges (the edges form a set, not a multiset). Both these problems mean that the claimed equivalence of hypergraphs, set systems and incidence structures is not true. What is really needed is a rewrite of the page to expose the major variations in the definition and their consequences. The main issues are: can there be multiple edges, can there be multiple vertices, can there be isolated vertices, can there be empty edges? I expect that all 2⁴ combinations have occured in the literature. McKay (talk) 02:32, 26 July 2008 (UTC)

Uses

What are hypergraphs used for? RJFJR (talk) 21:01, 22 February 2010 (UTC)
For instance, in knowledge representation, by people citing Wikipedia for reference. Therefore, I am annoyed by such vandalism.--Efidetum (talk) 19:45, 17 May 2010 (UTC)

The NYTimes had an example of a hypergraph, in describing relations among 2013 Oscar nominees: http://www.nytimes.com/interactive/2013/02/20/movies/among-the-oscar-contenders-a-host-of-connections.html (well, I guess that's a multi-hypergraph, since it has repeated edges). That example is behind a paywall (kinda); it'd be nice to have a [link to] a nice visual javascripty example like this, near the top of the article. — Preceding unsigned comment added by Not-just-yeti (talk • contribs) 18:22, 21 February 2013 (UTC)

Hypergraph drawing (circuit diagram)

I don't think the text under the circuit diagram example is true:

This circuit diagram can be interpreted as a drawing of a hypergraph in which four vertices (depicted as white rectangles and disks) are connected by three hyperedges drawn as trees.

— Hypergraph#Hypergraph_drawing

If you take the circuit components as vertices, you lose information about which terminals the wires/hyperedges are connected to. For example, the hypergraph of that circuit would be the same if the voltage source E was flipped around, but the circuit would most definitely not be the same (unless you also negated the voltage provided by E). Does anyone agree or disagree with me here? Hypergraph (talk) 01:48, 22 December 2010 (UTC)

Depends on what you are doing with the netlist. In the case of partitioning a netlist or placing of components, which pin is connected to which hyperedge does not matter, and these functions can use a pure hypergraph formulation. For circuit or logic simulation, you do care, and you now have a network of 'instance pins', each connected nets represented by hyperedges. For high performance logic, the delay through the wire itself matters, an each hyperedge needs to be replaced by a directed graph (or something even more complex) that describes the propagation of the signal through the wire itself. LouScheffer (talk) 16:26, 22 December 2010 (UTC)

Directed Hypergraph

There should probably be some mention of how a directed hypergraph is defined (i.e. a prescription for directed edges). — Preceding unsigned comment added by 50.99.141.142 (talk) 13:37, 12 June 2011 (UTC)

I second this. Also, some mention of a petri net and it's connection to hypergraphs. It also seems like undirected hypergraphs have some connection to the formal definition of a topological space and a well-ordered set, but I don't see mention of these. — Preceding unsigned comment added by 146.186.131.40 (talk) 20:53, 1 November 2012 (UTC)

Back in Jan 2021, I agreed with this and added a definition and some applications of directed hypergraphs. SoloUnEditor (talk) 15:43, 28 January 2024 (UTC)

goodfaith insertion

This paragraph was just added to the article (and reverted by me):

I believe that is is possible to think of a hypergraph as a Polygon mesh, where the edges are surfaces. A surface has many vertices, and a vertex has many surfaces. Someone please write this in mathematical terms. We aren't limited to 2 dimensional paper anymore.

One difference between the two concepts is that in a mesh it may be important that edges are shared by exactly two facets (something that affects me as I've just designed my first 3d print!). —Tamfang (talk) 23:20, 24 May 2012 (UTC)

Another difference is that a polygon mesh might be an example of a hypergraph, but a hypergraph is an abstract set system and therefore is not necessarily a polygon mesh. Zaslav (talk) 03:29, 10 July 2012 (UTC)

Terminology

I changed "link" (the alternate name of a hyperedge) to "edge", which is much more common in my experience. Maybe "link" can be added back, but it means something else in graph theory (a "link" is an edge that isn't a loop), and I'm not aware of its being used much (or at all) by hypergraph theorists. Zaslav (talk) 03:31, 10 July 2012 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Hypergraph/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Needs material on history, motivation, applications, current state of research, and relations with graphs and graph theory. Tompw (talk) 15:24, 4 January 2007 (UTC)

Last edited at 22:58, 19 April 2007 (UTC). Substituted at 02:13, 5 May 2016 (UTC)

Language

The article is just too verbose.

• Why do we have to mention a universal set in the lede? There's no link to universal set, but from that article i take away that universal sets are not very popular in formal logic.
• Why does the definition, titled §Terminology, use index set
• The type setting ie. the formatting in said section could use some make up, too, to become clearer and lighter.
• The $I$ in section "homomorphisms" isn't one of the previously mentioned index sets, is it? I don't know what the standards on maths articles are, but I guess the section is below standard. We do need to explain the notation if it isn't obvious and we shouldn't assume it was obvious unless a linked-to article explains it well, which in this case with "permutation" is not the case.

Regarding the Definition, index set is not used to explain anything in the article as far as I've scanned it. If the whole purpose is to introduce the notion of an index set, the heading title might be apt with "terminology", but it seems unmotivated. A clear definition is lacking, anyway, if that should be in the lede, the lede is far too long to be clear. The index set doesn't help to clarify anything, because x_i remains undefined (unbound?), even if $i\in I_{e}$ was defined. I propose:

Definition: H=(X,E), where X is the set of Vertices and E={e|e subseteq X}

although I am not sure if self-adjacent vertices are actually allowed or not as it currently stands. Certainly, the article is messy anyhow, following some comments on the talk page. I'm just curious if we can slowly improve it.91.66.71.216 (talk) 20:33, 14 June 2017 (UTC)

It's certainly possible that this article could be made less technical, and I'd welcome edits that accomplished that. But to answer some of your questions: the reason there's no link to universal set is that that article is about a different concept than the meaning here, which is just the union of the sets in the family. I think Universe (mathematics) is more relevant. And the use of an index set for the edges, at least, should be to allow more than one edge to have the same incident vertices, but the definition in our article doesn't actually achieve that, because it still says that the edges are sets and that the collection of edges is a set of sets. Your proposed replacement definition is wrong for the same reason. For what it's worth, Berge ("Hypergraphs", North Holland, 1989) defines a hypergraph to be a "family" of finitely many nonempty finite sets (E_1, E_2, ... E_m) whose union is the set of vertices of the hypergraph. So he allows repeated edges, allows single-vertex hyperedges, but does not allow isolated vertices and does not allow infinite hypergraphs. I'm sure other authors have varying definitions. —David Eppstein (talk) 21:08, 14 June 2017 (UTC)

I agree with the above comment that the article is too verbose. Although verbosity is not the only problem; the article is worded in a very difficult, math-centric way. I come from biology/bioinformatics and we also have hypergraphs in network topologies, yet the wikipedia article is almost useless to me, since it is way too complicated. It's ok to write about the mathematics behind, but the introduction, the header, should be MUCH simpler. So many other articles in wikipedia, including scientific ones, are simpler to read. I am not sure if this is a problem by those who wrote the page here or whether mathematicians like to "talk" through "formula first". 2A02:8388:1604:CA80:F462:6A60:DEA:83A0 (talk) 17:45, 9 October 2018 (UTC)

Undirected Graphs are wrong

The example directed graph is wrong as is all talk about it. An undirected hypergraph is *not* a a set of vertices and a set of edges which is a subset of P(V). The edges are pairs, just as with a graphs. The way undirected hypergraph was defined was simply as a subset of P(V) but that is just a subset of P(V) and not a hypergraph. A hypergraph is a graph on hypervertices(which are elements of P(V)). That is, edges in the graph on the hypervertices are hyperedges in the hypergraph. E should look something like E = {(e1,e2),(e1,e3)} where ek is the sets given in the picture. Edges can be thought of as lines/edges/connections/morphisms between subsets. 173.173.45.154 (talk) 11:39, 27 February 2023 (UTC)

The first sentence above says "directed", do you mean "undirected"?

I expanded directed hypergraphs on this page in Jan 2021. Having just revisited the page I am also now rather unsure that the definition of undirected hypergraph makes sense, and should probably instead be undirected connections between two sets of vertices. I'll be happy to update the page myself, or you can do so, but it will help me if you can give here a reference for your definition? SoloUnEditor (talk) 15:48, 28 January 2024 (UTC)

I was also confused between the mismatch between the intro paragraph which mentions pairs and the example on the right which doesn't have any pairs. So I'd welcome those edits! Either way, what's an authoritative source setting out this definition? Golightlys (talk) 17:24, 25 July 2024 (UTC)

The paragraph that mentions "pairs" is about directed hypergraphs, which is in bold. There is an example on the right, but you have to scroll all the way past the undirected example. It has pairs of (from, to), and each of from and to are a set of vertices.

The definition of undirected hypergraphs is pretty universal: they are a generalisation of undirected graphs (which have edges with two vertices), such that their (hyper)edges have any number of vertices. This means that after quite a bit of consideration, my thought above, that they should have (hyper)edges that are between two sets of vertices, is wrong - sorry about that. I'm about to add a ref for the "hyperedge = any number of vertices" definition. SoloUnEditor (talk) 00:46, 30 August 2024 (UTC)

issue

There is a formal definition of "directed hypergraph" but no formal definition of "hypergraph". Saying that is a generalization of "graph" only helps a little; for example it doesn't say if edges can be the same (as each other), which impacts whether every bicoloured graph can be considered the incidence graph of a hypergraph. McKay (talk) 06:17, 17 March 2023 (UTC)

I would say that if a directed hypergraph is a generalisation of a directed simple graph, then whether the start and end of a hyperedge can be the same is the same question as for a directed simple graph: are loops allowed for that graph? But spelling that out in the page seems like a good idea. SoloUnEditor (talk) 15:50, 28 January 2024 (UTC)