Realiziability of hypergraphs as link (multi)sets of ordinary graphs

Question

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.

Answer 1

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.