patternMinor
How is a hypergraph different from a bipartite graph?
Viewed 0 times
graphbipartitedifferenthypergraphhowfrom
Problem
How is a hypergraph different from the bipartite graph generated from the hypergraph by introducing new vertices for each hyperedge, and connecting these vertices with the vertices connected by the original hyperedge. Alternatively, I could also start with a bipartite graph, designate one of the sets of vertices as the hyperedges, and connect these hyperedges with the vertices connected to the original vertices.
Is there anything wrong with this construction? Are there theorems about hypergraphs that don't have a natural interpretation in terms of the bipartite graph just described?
I haven't read in detail what vzn is proposing here, but this got me interested in the question whether hypergraphs are really non-trivial generalizations of graphs. I googled for hypergraphs (and Wikipedia indeed also described the construction given above) and searched stackexchange and mathoverflow, but somehow hypergraphs are always treated as a non-trivial generalization of graphs, and somehow considered to be much more complicated than graphs. Don't read too much into this question, I have neither done an excessive literature research nor thought too deeply about hypergraphs. (Perhaps I even accidentally searched for multigraph instead of hypergraph, but I don't think so.)
Is there anything wrong with this construction? Are there theorems about hypergraphs that don't have a natural interpretation in terms of the bipartite graph just described?
I haven't read in detail what vzn is proposing here, but this got me interested in the question whether hypergraphs are really non-trivial generalizations of graphs. I googled for hypergraphs (and Wikipedia indeed also described the construction given above) and searched stackexchange and mathoverflow, but somehow hypergraphs are always treated as a non-trivial generalization of graphs, and somehow considered to be much more complicated than graphs. Don't read too much into this question, I have neither done an excessive literature research nor thought too deeply about hypergraphs. (Perhaps I even accidentally searched for multigraph instead of hypergraph, but I don't think so.)
Solution
Essentially, a hypergraph may be "nice" in some sense, but there may be no equivalent (or at least natural) corresponding notion of niceness for the associated bipartite graph.
One way to approach the question is by analogy with graphs. Every graph can be represented by its incidence graph, a bipartite graph with vertices in one partition, and edges in the other. Yet we seldom want to use this "standardised" bipartite representation of graphs, for a variety of reasons. The same reasons (and more) apply to keeping hypergraphs as they are.
You comment below that this analogy with the graph case was your starting point. Perhaps we have a different set of intuitions about why turning every graph into a bipartite graph is unnatural, so instead let me try another tack.
First, there are many different notions of what a hypergraph is, depending on the application.
One rather general definition is a set system, which allows the set of edges of the hypergraph to be a subset of the powerset of the vertices. This allows empty edges, edges with size one, edges that are strictly contained in other edges, and some vertices may also not participate in any edge. There are versions of hypergraphs that disallow some combination of each of these "features". These features are important for some applications, and authors tend to rely on them implicitly, so it is worth checking the definition each time.
The best reference I know is Berge's book. Note that it is essentially a reprint of the second half of his 1973 book on graphs and hypergraphs, and is quite hard to use: it is a useful reference but I can't wholeheartedly recommend it. Berge requires in a hypergraph that there are no empty edges and that every vertex should be part of some edge, but allows repeated edges (giving a multiset of subsets of the powerset). He calls a hypergraph with no edge contained in another a simple hypergraph.
If one disallows edges that are contained in other edges, but allows empty or singleton edges and repeated edges, then the dual graph of the hypergraph that you describe (usually called the incidence graph of the hypergraph, or sometimes referred to as its Levi graph) is a bipartite graph. Further, the hypergraph can be reconstructed from its incidence graph.
Sometimes this is perfectly appropriate. However, useful things do get scrambled if one breaks this particular shell. As an example, various notions of colouring are interesting for hypergraphs, but these are highly unnatural in the bipartite graph setting. Many other properties of classes of hypergraphs are also scrambled going to the incidence graph.
Perhaps the best part of Berge's book is its continual insistence (with many examples) that hypergraphs really are worth studying, and that they do nontrivially extend graphs.
Edit: clarified terminology, as suggested by vzn's answer.
One way to approach the question is by analogy with graphs. Every graph can be represented by its incidence graph, a bipartite graph with vertices in one partition, and edges in the other. Yet we seldom want to use this "standardised" bipartite representation of graphs, for a variety of reasons. The same reasons (and more) apply to keeping hypergraphs as they are.
You comment below that this analogy with the graph case was your starting point. Perhaps we have a different set of intuitions about why turning every graph into a bipartite graph is unnatural, so instead let me try another tack.
First, there are many different notions of what a hypergraph is, depending on the application.
One rather general definition is a set system, which allows the set of edges of the hypergraph to be a subset of the powerset of the vertices. This allows empty edges, edges with size one, edges that are strictly contained in other edges, and some vertices may also not participate in any edge. There are versions of hypergraphs that disallow some combination of each of these "features". These features are important for some applications, and authors tend to rely on them implicitly, so it is worth checking the definition each time.
The best reference I know is Berge's book. Note that it is essentially a reprint of the second half of his 1973 book on graphs and hypergraphs, and is quite hard to use: it is a useful reference but I can't wholeheartedly recommend it. Berge requires in a hypergraph that there are no empty edges and that every vertex should be part of some edge, but allows repeated edges (giving a multiset of subsets of the powerset). He calls a hypergraph with no edge contained in another a simple hypergraph.
- Claude Berge, Hypergraphs: Combinatorics of Finite Sets, 1989, Elsevier.
If one disallows edges that are contained in other edges, but allows empty or singleton edges and repeated edges, then the dual graph of the hypergraph that you describe (usually called the incidence graph of the hypergraph, or sometimes referred to as its Levi graph) is a bipartite graph. Further, the hypergraph can be reconstructed from its incidence graph.
Sometimes this is perfectly appropriate. However, useful things do get scrambled if one breaks this particular shell. As an example, various notions of colouring are interesting for hypergraphs, but these are highly unnatural in the bipartite graph setting. Many other properties of classes of hypergraphs are also scrambled going to the incidence graph.
Perhaps the best part of Berge's book is its continual insistence (with many examples) that hypergraphs really are worth studying, and that they do nontrivially extend graphs.
Edit: clarified terminology, as suggested by vzn's answer.
Context
StackExchange Computer Science Q#12769, answer score: 5
Revisions (0)
No revisions yet.