Papers^γ / Sergey Kirgizov

I wonder if we can obtain asymptotic results in the same manner...

A related [question](https://mathoverflow.net/questions/384683/random-permutations-without-double-rises-avoiding-consecutive-pattern-underli/384947#384947) on Mathoverflow.

The article provides an extension of Boltzmann sampling to the realm of labeled combinatorial structures, enumerated by exponential generating functions and constructed using the box product. ---- [Boltzmann sampling](https://en.wikipedia.org/wiki/Boltzmann_sampler) is a general, pretty fast, technique for generate uniformely random combinatorial structures specified by structural equations. The key idea of Boltzmann sampling can be illustrated by the following example. Suppose you have a generating function $$f(x) = x + x^2 + x^2 + x^3 + x^3 + x^3 + x^3 + x^4 ...$$ corresponding to the one object of size one, two objects of size 2, four objects of size 3, etc. If you set, for example, $x = \frac{1}{2}$ then $$f\left(\frac{1}{2}\right) = \frac{1}{2} + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 ...$$ Now let's take $x$ such that $f(x) < \infty$, and chose an integer $k$. As you think, it quickly becomes clear that you can use this to chose a random object of size $k$. The probability equals precisely $\frac{x^k}{f(x)}$. For a given $k$ it is uniform. The elaboration of this idea in the context of structural equations (a.k.a. recursive decompositions, [symbolic method](https://en.wikipedia.org/wiki/Symbolic_method_%28combinatorics%29)) leads you to Boltzmann sampling technique. And knowing the values of generating functions together with corresponding recursive decompositions will allow you to generate a random object according to a uniform probability measure for any size. Shifting $x$ you will shift the mean size of a generating object. See [Boltzmann Samplers For The Random Generation Of Combinatorial Structures](https://www.researchgate.net/publication/2562585_Boltzmann_Samplers_For_The_Random_Generation_Of_Combinatorial_Structures) paper by Duchon, Flajolet, Louchard and Schaeffer for such elaboration.

See also these 2 related questions on MathOverflow: https://mathoverflow.net/questions/384683/random-permutations-without-double-rises https://mathoverflow.net/questions/14863/random-alternating-permutations

Hello, are you aware of any open source implementation of this algorithm ?

Some nice presentations on the topic: - https://www.irif.fr/~habib/Documents/cours_4-2015.pdf - http://igm.univ-mlv.fr/AlgoB/algoperm2012/04Paul.pdf - http://www.lirmm.fr/~paul/Talks/talk-06-algo-sem-McGill.pdf

>See table 3 from https://arxiv.org/abs/1811.10705 This is with $n=50$ nodes. It seems that the behavior is not the same for $n$ large: - I think that in a large ER, if the proba of connection $p$ is not too large or too small, then it is rare to find a group of nodes with the same neighbors outside the group (i.e. find a module). Can you prove that? - I don't think that the code https://github.com/antonovvk/decmod is buggy.

[Almost all finite graphs are asymmetric](https://en.wikipedia.org/wiki/Asymmetric_graph#Random_graphs). There is no pair of vertices with common neighborhood.