Monday, May 11, 2009

Requst for Info on Prob Hypergraphs

A grad student recently asked me for some refs on probabilistic hypergraphs. I didn't know any, but I suggested we harness the power of the internet and of the blog. Here are his questions. If you know any refs please comment.

(Here are his questions.)

I have a problem that deals with coalitions. The basic idea is to have a hypergraph with a bunch of nodes representing actors and edges representing coalitions. Such a hypergraph would have the following properties:
  1. non-regular (edges can have any number of nodes, and different edges in the same graph can have different numbers of nodes)
  2. down-set (the existence of an edge implies the existence of all edges that are a subset of that edge)
  3. finite
  4. probabilistic EDGES (I had found previous work on probabilistic nodes, but not for edges)
Does anyone know of any work on these types of hypergraphs? ~
Posted by at

4 comments:

  1. Saugata Basu12:58 PM, May 11, 2009

    Such a hypergraph would have the following properties: non-regular (edges can have any number of nodes, and different edges in the same graph can have different numbers of nodes) down-set (the existence of an edge implies the existence of all edges that are a subset of that edge)It would be more natural to call this object a random simplicial complex (which is what it is) rather than call it a hypergraph. (Btw, this of course leads to the philosophical question of why call one dimensional complexes "graphs", especially since the word graph is already overloaded in mathematics by its use as in "graph of a map"). Coming back to the original question: I believe that I have seen some work on the expected Betti numbers of such random complexes. In fact its probably worthwhile to check out the following reference:

    R. Meshulam and N. Wallach, Homological connectivity of
    random k-dimensional complexes,
    Random Struct. Algorithms 34(2009) 408-417.

    ReplyDelete
  2. KönigHall2:52 PM, May 11, 2009

    any particular reason not to model this situation using (random) bipartite graphs?

    ReplyDelete
  3. Anonymous5:52 PM, May 11, 2009

    I agree -- abstract simplicial complexes can be modeled by graphs, although it may well be less technically tricky to just use a hypergraph.

    ReplyDelete
  4. Anonymous8:42 PM, May 11, 2009

    Having used some of both (hypergraphs and simplicial complexes), I would say that the extra structure afforded by the use of simplicial complexes far outweighs any notion that "hypergraphs are simpler." I'm not even sure I agree with that notion, particularly in the case when your hypergraph's edges are explicitly downward closed, which is exactly the condition needed for it to be a simplicial complex.

    --Anon. 2

    ReplyDelete

Subscribe to: Post Comments (Atom)