Papers^γ

Algorithm 1 makes me think of Algorithm 3 [here](https://www-complexnetworks.lip6.fr/~latapy/Publis/triangles_short.pdf)

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.

Nice paper! Very clear and useful!! I do not see absolute time values in the experiments, just speedups. It would have been nice to show some absolute values too. I've implemented the algorithms [here](https://github.com/maxdan94/ParallelUnionFind). On a very large graphs with more than 10 billions of edges (the twitter graph [here](https://sites.google.com/view/limass/datasets)), I observe that the verification algorithm is faster and leads to better speedups than the lock algorithm.

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