I started studying hypergraphs theory some days ago.
I know that a hypergraph is a tuple $H = (X, E)$, in which $E \subseteq \mathcal{P}(X)$ and is actually a generalisation of the notion of graph.
Though, I'm wondering why they're useful. I saw this example of this paper. They explain how in the first sample I can't discern whether an author wrote more than one article, whereas in the second one (with the hypergraph representation) I can easily get this information.
But this is not true, right? I can always attach the information on the edges or nodes to compute that. In addition, from what I understood, I can always represent hyperedges $e \in E$ as cliques, right? Hence, I can always (?) transform an hypergraph to a graph. I must be wrong.
My questions are:
- Is the notion of hypergraphs really necessary?
- Do hypergraphs and graphs have the same expressivity?
- Can I represent something with hypergraphs which I can not with graphs?
If you try really hard, you can express anything with graphs, especially if you let yourself attach information to vertices or edges to help.
The way you're suggesting - replacing each hyperedge by a clique - is not the best. In this way, you can't distinguish the hyperedge $\{1,2,3,4,5\}$ from the three hyperedges $\{1,2,3\}$, $\{3,4,5\}$, and $\{1,2,4,5\}$. You have to have a graph with an edge-labeling saying which hyperedge each clique comes from, and that's awkward.
The standard way to represent hypergraphs as graphs is with the incidence graph. Given a hypergraph $(X,E)$, its incidence graph is the bipartite graph with vertices $X$ on one side, vertices $E$ on the other side, and an edge $xe$ if $x \in e$ in the hypergraph.
Via this representation, (multi-)hypergraphs are actually equivalent to bipartite graphs (with a designated "$X$" side and "$E$" side). Any multi-hypergraph gives a bipartite graph, and any bipartite graph gives a multi-hypergraph. Theorems about one can be turned into theorems about the other.
Sometimes we use hypergraphs anyway, because a concept is easier to express for the hypergraph than it is for the incidence graph. Many theorems about graphs have natural generalizations to hypergraphs, and representing them as incidence graphs is very unnatural.