I have a question about hypergraphs that I hope some combinatorics/graph theory experts can answer. The motivation for this question is group-theoretic and comes from the study of a certain space of measures that comes equipped with a natural affine action of the group Out(F\_n). I'll skip the detailed background here, but if someone is interested, please look-up my paper with Tatiana Nagnibeda arXiv:1105.5742


Let G be a finite simple graph. For every vertex v of G the link Lk(v) is the set of vertices adjacent to v. Now form a weighted hypergraph Lk(G) whose vertex set is the same as the vertex set of G and whose hyper-edges are exactly all sets Lk(v) as v varies over the vertex set of G. Every hyperedge E in Lk(G) comes with a positive integral "weight" w(E) which is the number of vertices of G such that Lk(v)=E.


Now suppose we are given a finite weighted hypergraph H with positive integral weights on its hyperedges. 
I'd like to know if there are known necessary and sufficient condition for H so that there exists a graph G such that H=Lk(G).


If anyone knows the answer or has some suggestions regarding where to look, I'd much appreciate it.


Thanks a lot,


Ilya Kapovich.



Realiziability of hypergraphs as link (multi)sets of ordinary graphs 
Let $A(H) = (a\_{ij})$ be the incidence matrix of a weighted hypergraph $H$. This is the 0-1 matrix such that $v\_i \in E\_j$ if and only if $a\_{ij} = 1$. (Repeated hyperedges from the integral weighting result in repeated columns of the matrix.) Then $H = Lk(G)$ for some graph $G$ if and only if the columns (or rows) can be permuted to form a symmetric matrix.


(I don't know if this is well known or not. If it's a common construction, I'm sure it is known.)


Let $G$ be a graph. Then we have:


$$v\_i \in Lk(v\_j) \iff v\_j \in Lk(v\_i)$$


As long as we label the edges so that $E\_i = Lk(v\_i)$, the incidence matrix is symmetric.


In the other direction, let $A'$ be a symmetric matrix resulting from permuting the columns of $A(H)$. Form $G$ by requiring that $v\_i$ and $v\_j$ be adjacent if and only if the $a\_{ij}$ entry of $A'$ is 1. Then $E\_j'$ consists of the vertices in $G$ adjacent to $v\_j$. It follows that $H = Lk(G)$.


For loopless graphs we do have to add the condition that the matrix be permutable to one with 0's along the diagonal.


