6 citations · 7 across the 3 of their papers we have counts for
7 papers
Counting directed acyclic and elementary digraphs
Élie de Panafieu, Sergey Dovgal
Directed acyclic graphs (DAGs) can be characterised as directed graphs whose strongly connected components are isolated vertices. Using this restriction on the strong components, w…
The birth of the contradictory component in random 2-SAT
Sergey Dovgal
We prove that, with high probability, the contradictory components of a random 2-SAT formula in the subcritical phase of the phase transition have only 3-regular kernels. This foll…
Symbolic method and directed graph enumeration
Élie de Panafieu, Sergey Dovgal
We introduce the arrow product, a systematic generating function technique for directed graph enumeration. It provides short proofs for previous results of Gessel on the number of…
Statistical properties of lambda terms
Maciej Bendkowski, Olivier Bodini, Sergey Dovgal
We present a quantitative, statistical analysis of random lambda terms in the de Bruijn notation. Following an analytic approach using multivariate generating functions, we investi…
Asymptotic Distribution of Parameters in Random Maps
Olivier Bodini, Julien Courtiel, Sergey Dovgal +1
We consider random rooted maps without regard to their genus, with fixed large number of edges, and address the problem of limiting distributions for six different parameters: vert…
Polynomial tuning of multiparametric combinatorial samplers
Maciej Bendkowski, Olivier Bodini, Sergey Dovgal
Boltzmann samplers and the recursive method are prominent algorithmic frameworks for the approximate-size and exact-size random generation of large combinatorial structures, such a…