3
$\begingroup$

The theory of random graphs, after the pioneering classic work of Erdős & Rényi, has come to prominence with many further refinements, most notably the small world theory (Barabási, Watts, etc).

I have been wondering for a while if someone has attempted to generalize it to higher dimensions (hypergraphs), in a systematic way.

Notice that I have used the expression in a systematic way deliberately:

attempts to study random hypergraphs have been carried out, for instance here

What I have in mind, though, is a taxonomy of random hyper-graphs (particularly random simplicial sets, but not only), and their corresponding geometric realizations keyed on various probability rules for adding n-dimensional hyper-edges on the basis of what already happened below (ie in lower dimensions).

Is there such a study?

ADDENDUM: to avoid ambiguity, and/or the impression of a too vague/loose question: here is what I am looking for

  1. Any references to articles, conference talks, and what else whose theme is the generalization of Random Graph Theory to hyper-graphs

  2. Proposals of new laws which will govern the probability of adding hyper-edges (beyond the trivial case, which essentially would do in higher dimensions what the original Erdős & Rényi "uniformly random graphs" did).

  3. More ambitiously, conjectures/theorems that, based on 2, formulate average laws as to the nature of the random hyper-graphs

  4. Conceptual frameworks (for instance using higher category theory) where a general theory of Random HyperGraphs can be formulated and properly set.

  5. Finally, anything from 1 to 4 in the restricted case of Random Simplicial Sets

$\endgroup$

1 Answer 1

3
$\begingroup$

Perhaps this 2011 talk at the Workshop on Random Graphs is at least tangentially related to your interests:

"Beyond random graphs: Random simplicial complexes. Applications to sensor networks" by L. Decreusefond, E. Ferraz, P. Martins, H. Randriambololona, A. Vergne (PDF link)

Here is one of their most colorful slides:
           RandomSimplicialComplexes

You might also look at:

  • The earlier MO question on Random Manifolds.
  • The work of Matthew Kahle, e.g.,
    • "Limit theorems for Betti numbers of random simplicial complexes" (link), or
    • Topology of Random Simplicial Complexes and Phase Transitions for Homology (Google Books link).

Here is the abstract of this last reference, which is perhaps the most direct hit on your concerns:

To measure the connectivity of our random simplicial complexes, we compute various facts about their expected homology and homotopy groups. One complication for the complexes we study is that in contrast to the Erdős-Renyi setting, vanishing of homology does not correspond to any monotone graph property. Nevertheless, we still see higher dimensional analogues and generalizations of the Erdős-Renyi threshold for connectivity of $G(n, p)$. It is also shown in each setting that the number of nontrivial homology groups is small compared to the dimension of the complex itself.

$\endgroup$
1
  • $\begingroup$ Yes Joseph, this talk looks like something right up my alley. And so do the other links. Thanks! $\endgroup$ Jan 6, 2013 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.