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.

[For an excellent survey of results on graph complexes, see Simplicial Complexes of Graphs, by Bjorner's student, Jakob Jonsson.]

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.)

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.

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?

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.

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.

  • $\begingroup$ It's worth noting that the property of being a clutter at all is a monotone hypergraph property, so the set of clutters forms a subcomplex of the simplex on $2^n$ vertices mentioned above. An alternate answer to the first question then would be to answer, "What's the homotopy type/topological structure on the subcomplex of all clutters?" Are there better simplicial representations of clutters than this? What about simplicial representations when the hypergraph is viewed as a simplicial complex? $\endgroup$ – Gwyn Whieldon Apr 1 '10 at 20:29
  • $\begingroup$ Can you give some examples of what kind of property you're thinking about? In particular, do they satisfy a stronger monotonicity condition where deleting a face and adding back any collection of sub-faces preserves the property? $\endgroup$ – Dylan Thurston Apr 2 '10 at 4:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.