Realiziability of hypergraphs as link (multi)sets of ordinary graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:44:31Z http://mathoverflow.net/feeds/question/100495 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100495/realiziability-of-hypergraphs-as-link-multisets-of-ordinary-graphs Realiziability of hypergraphs as link (multi)sets of ordinary graphs Ilya Kapovich 2012-06-24T00:11:14Z 2012-06-24T08:26:38Z <p>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</p> <p>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.</p> <p>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).</p> <p>If anyone knows the answer or has some suggestions regarding where to look, I'd much appreciate it.</p> <p>Thanks a lot,</p> <p>Ilya Kapovich.</p> http://mathoverflow.net/questions/100495/realiziability-of-hypergraphs-as-link-multisets-of-ordinary-graphs/100502#100502 Answer by Hugh Denoncourt for Realiziability of hypergraphs as link (multi)sets of ordinary graphs Hugh Denoncourt 2012-06-24T05:34:58Z 2012-06-24T05:34:58Z <p>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.</p> <p>(I don't know if this is well known or not. If it's a common construction, I'm sure it is known.)</p> <p>Let $G$ be a graph. Then we have:</p> <p>$$v_i \in Lk(v_j) \iff v_j \in Lk(v_i)$$</p> <p>As long as we label the edges so that $E_i = Lk(v_i)$, the incidence matrix is symmetric.</p> <p>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)$.</p> <p>For loopless graphs we do have to add the condition that the matrix be permutable to one with 0's along the diagonal.</p>