6 citations · 10 across the 7 of their papers we have counts for
11 papers
Exact enumeration of satisfiable 2-SAT formulae
Sergey Dovgal, Élie de Panafieu, Vlady Ravelomanana
We obtain exact expressions counting the satisfiable 2-SAT formulae and describe the structure of associated implication digraphs. Our approach is based on generating function mani…
The birth of the strong components
Sergey Dovgal, Élie de Panafieu, Dimbinaina Ralaivaosaona +2
Random directed graphs undergo a phase transition around the point , and the width of the transition window has been known since the works of Luczak and Seierstad…
Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
Maciej Bendkowski, Olivier Bodini, Sergey Dovgal
Combinatorial samplers are algorithmic schemes devised for the approximate- and exact-size generation of large random combinatorial structures, such as context-free words, various…
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…
Shifting the Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints
Sergey Dovgal, Vlady Ravelomanana
We show that by restricting the degrees of the vertices of a graph to an arbitrary set \( Δ\), the threshold point of the phase transition for a random graph with ve…
Towards Model Selection for Local Log-Density Estimation. Fisher and Wilks-type theorems
Sergey Dovgal
The aim of this research is to make a step towards providing a tool for model selection for log-density estimation. The author revisits the procedure for local log-density estimati…