Asked By : Thomas Klimpel
Answered By : vzn
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:
- Fractional Graph Theory A Rational Approach to the Theory of Graphs Scheinerman, Ullman (2008)
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