How is a hypergraph different from a bipartite graph?

Problem Detail: 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.)

Asked By : Thomas Klimpel

Answered By : vzn

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12769