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

2012-06-24T00:11:14Z

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 by Hugh Denoncourt for Realiziability of hypergraphs as link (multi)sets of ordinary graphs

2012-06-24T05:34:58Z

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.

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

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

Answer by Hugh Denoncourt for Realiziability of hypergraphs as link (multi)sets of ordinary graphs