1
$\begingroup$

I am wondering if anyone can indicate whether the following is a solved problem. I don't care about time of the algorithm currently.

Consider a general probability distribution F on simple graphs with number of vertices n. The distribution is exchangeable on vertices.

In general, how can we sample from such a distribution on simple graphs with number of vertices N, such that if we pick any n vertices out of N, the corresponding probability distribution on the subgraph is F? Asymptotic distribution is also acceptable.

I am also curious about existence and uniqueness of the distribution.

Improve this question
$\endgroup$
4
  • $\begingroup$ If $F$ gives 0 probability to empty sets and complete graphs, Ramsey's theorem says there are no such graphs for very large $N$. More general versions of Ramsey's theorem eliminate more cases. The existence question is indeed interesting. I feel that the theory of pseudorandom graphs may be relevant. $\endgroup$
    – Brendan McKay
    Commented Jan 26, 2016 at 23:30
  • $\begingroup$ Thank you! I am sure that the distribution I am looking at gives positive probability to any possible simple graphs...Would you give me some sources that I can look at? $\endgroup$
    – lonelygopher
    Commented Jan 26, 2016 at 23:36
  • $\begingroup$ A nice survey of pseudorandom graphs is at people.math.ethz.ch/~sudakovb/pseudo-random-survey.pdf . It isn't my field so I'm not sure how much it will help. $\endgroup$
    – Brendan McKay
    Commented Jan 26, 2016 at 23:39
  • $\begingroup$ For my purpose F doesn't need to be Erdos-Renyi at all. What I am actually looking at is here...en.wikipedia.org/wiki/Exponential_random_graph_models Anyway, I realized how this problem could be...Thanks. You have been very helpful. $\endgroup$
    – lonelygopher
    Commented Jan 27, 2016 at 0:03

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .