Simplicial Representations of (Hyper)Graph Complexes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T06:12:15Z http://mathoverflow.net/feeds/question/20098 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20098/simplicial-representations-of-hypergraph-complexes Simplicial Representations of (Hyper)Graph Complexes Gwyn Whieldon 2010-04-01T19:38:55Z 2010-04-05T14:26:39Z <p>For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, this family forms a subcomplex of the simplex on $\binom{n}{2}$ vertices, with each vertex corresponding to an edge and each face in the simplex corresponding to a particular graph [where the dimension of the face is precisely the number of edges in the graph minus 1.] The family being closed under deletion of edges translates nicely into the family (a set of faces) truly being a subcomplex. As a result, each monotone graph property corresponds to a tangible, often combinatorially interesting simplicial complex.</p> <p>[For an excellent survey of results on graph complexes, see <a href="http://www.amazon.com/Simplicial-Complexes-Graphs-Lecture-Mathematics/dp/3540758585" rel="nofollow">Simplicial Complexes of Graphs,</a> by Bjorner's student, Jakob Jonsson.]</p> <p>For pure dimensional hypergraphs, a similar subcomplex can be constructed. A (d-1)-dimensional pure hypergraph family will sit as a subcomplex inside a simplex of dimension $\left(\binom{n}{d}-1\right)$, now with each vertex in the simplex corresponding to a (d-1)-dimensional face - so again, any monotone (pure) hypergraph property can be examined via topology of these complexes. Unfortunately, many properties that are monotone for graphs fail to be monotone for hypergraphs (not-connectivity in codimension 1 for pure hypergraphs in dimension 2 or higher immediately springs to mind, among others.)</p> <p>Hypergraphs in general, however, need not be pure, and several interesting classes of them most certainly are not. A hypergraph complex is just any family of hypergraphs closed under the deletion of edges.</p> <p>Is there any standard way of simplicially representing hypergraph complexes which are not pure? There is a somewhat poor way of doing it, it seems, by considering the simplex on $2^n$ vertices and allowing each face to correspond to a hypergraph which is not necessarily a clutter (i.e. no edges in the hypergraph are properly contained inside other edges.) This is unsatisfying to put it mildly, however, and I was hoping there was an alternate way of considering hypergraph complexes as a topological space. Any ideas or literature references?</p> <p>Edit: Although I'm interested in a better geometric representation of hypergraph complexes for its own sake, the first main application would be for either "matchings" (or, alternately, noncrossing partitions) on hypergraphs. A matching on a graph is just a set of edges which are pairwise disjoint. The matching complex (of a graph G) sits as a subcomplex inside the complex of all graphs above, and consists of all such sets of edges. The general matching complex on n vertices is a special case of this, with $G=K_n$, the complete graph.</p> <p>For a hypergraph G, a matching can be defined equivalently - a subset of edges (now possibly with more than 2 vertices per edge) which are pairwise disjoint. The complete hypergraph (which is NOT a clutter, as its edges are all subsets) has a matching complex whose maximal faces correspond to all partitions of $[n]={1,2,...,n}$. This isn't precisely a complex of the form suggested below (one closed under the removal of a face, then the addition of any set of subfaces.) However, it is closed under the removal of a face and the addition of any disjoint set of subfaces.</p>