2
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Could you define hypergraph? I'm not familiar with the concept, and I don't think it's all too standard. $\endgroup$ – jmite Jun 19 '13 at 23:22
  • $\begingroup$ @jmite I added a link to wikipedia now. I'm not sure whether adding a definition directly to the question would be a good idea. After all, I'm looking for explanations from someone who is at least a bit familiar with this concept. $\endgroup$ – Thomas Klimpel Jun 19 '13 at 23:31
1
$\begingroup$

in math/cs in a sense many different objects can be seen as equivalent to other types of objects, but it seems more "natural" to study certain forms in certain contexts. for example a hypergraph is equivalent to a set of bitvectors, a SAT formula is also, etcetera.

is there anything wrong with this construction?

cant actually follow your descriptions from your words. you need to use mathematical notation, but yes in general one can convert between hypergraphs and graphs using different natural schemes. in fact that is part of many theorems on the subject of hypergraphs is ironing out these subtleties, finding the hypergraph "analogs" of basic graph theorems. and notice that two objects are equivalent if you can show there are functions ("constructions") $f,f^{-1}$ such that $f(x)=y$ and $f^{-1}(y)=x$ ie a mapping and an inverse, which you didnt actually sketch out.

wikipedia actually does give such a construction for "the bipartite graph model of hypergraphs" ie converting it to the incidence graph of the hypergraph.

Are there theorems about hypergraphs that don't have a natural interpretation in terms of the bipartite graph just described?

a ref I should perhaps have cited in that post which inspired it to some degree, which seems to me very comprehensive, wideranging, and pointing to some future developments, and should answer this question in a more general way—ie "why hypergraphs" versus other approaches—is:

an interesting perspective on hypergraphs is that in a sense they are a "fractional" generalization of "integer" graphs. in other words, a kind of "apparently natural" generalization in the way that fractional numbers are a generalization of integers. from p.viii, which also links it in to other trends in math:

This example illustrates the theme of this book, which is to uncover the rational side of graph theory: How can integer-valued graph theory concepts be modified so they take on nonintegral values? This “fractionalization” bug has infected other parts of mathematics. Perhaps the best known example is the fractionalization of the factorial function to give the gamma function. Fractal geometry recognizes objects whose dimension is not a whole number [126]. And analysts consider fractional derivatives [132]. Some even think about fractional partial derivatives!

to further quote from the introduction by Berge:

By developing the fractional idea, the purpose of the authors is multiple: first, to enlarge the scope of applications in Scheduling, in Operations Research, or in various kinds of assignment problems; second, to simplify. The fractional version of a theorem is frequently easier to prove than the classical one, and a bound for a “fractional” coefficient of the graph is also a bound for the classical coefficient (or suggests a conjecture). A striking example is the simple and famous theorem of Vizing about the edge-chromatic number of a graph; no similar result is known for the edge chromatic number of a hypergraph, but the reader will find in this book an analogous statement for the “fractional” edge-chromatic number which is a theorem. The conjecture of Vizing and Behzad about the total chromatic number becomes in its fractional version an elegant theorem.

so in short one can indeed apparently prove some novel ideas with hypergraphs that are not really yet formulated in terms of graphs and one would expect this trend to continue in active research. but note that graph theory plays a core role in hypergraphs. so in a sense there are the apparent beginnings of many bridge theorems.

another interesting angle that shows recent advance and possibly some future promise in the area: Fields-prize winning Gowers somewhat recently generalized the Szemeredi regularity lemma to hypergraphs. Szemeredi recently won the Abel prize (2012) in part for that work.

$\endgroup$
3
$\begingroup$

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.

  • 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.

$\endgroup$
  • $\begingroup$ Even so I like your answer overall, the first paragraph seems strange to me. In fact, similar statements lead to my confusion about hypergraphs in the first place, and caused me to ask this question. A hypergraph is a generalization of a graph, so of course a graph can be represented by a bipartite graph, if a hypergraph can. In the same way, a digraph is a non-trivial generalization of a graph, and the representation of a graph by its equivalent digraph is standard without anybody claiming that it would lead to serious drawbacks or that you shouldn't do it. $\endgroup$ – Thomas Klimpel Jun 20 '13 at 6:32

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.