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.

  • $\begingroup$ It looks like the Fano plane is not the link hypergraph of a simple graph, but it is the link hypergraph of a graph with loops. Is the lack of loops important? $\endgroup$ – Douglas Zare Jun 24 '12 at 0:47

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.

  • 1
    $\begingroup$ Right, and that means it is NP-complete to decide if a hypergraph arises from a graph, see cs.anu.edu.au/~bdm/papers/ColbournMcKaySymmetrizability.pdf . $\endgroup$ – Brendan McKay Jun 24 '12 at 7:11
  • $\begingroup$ OK, great, thanks! The answer is easier than I thought it might be, which is good news for me. Ultimately, I need to deal with the situation where both loop-edges and multiple edges are allowed in G (that is, G is an arbitrary one-dimensional finite CW-complex), but as far as I can tell the above characterization works in that context as well. $\endgroup$ – Ilya Kapovich Jun 24 '12 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.