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$ Apr 1, 2010 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$ Apr 2, 2010 at 4:22


Your Answer

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

Browse other questions tagged or ask your own question.