All the available preprints are collected on arXiv.
Additional bibliometric information can be found on my google scholar webpage.
Journals
4. The birth of the strong components (with Élie de Panafieu, Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, and Stephan Wagner)
Abstract
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. They have established that as when , the asymptotic probability that the strongly connected components of a random directed graph are only cycles and single vertices decreases from to as goes from to .
By using techniques from analytic combinatorics, we establish the exact limiting value of this probability as a function of μ and provide more properties of the structure of a random digraph around, below and above its transition point. We obtain the limiting probability that a random digraph is acyclic and the probability that it has one strongly connected complex component with a given difference between the number of edges and vertices (called excess). Our result can be extended to the case of several complex components with given excesses as well in the whole range of sparse digraphs.
Our study is based on a general symbolic method which can deal with a great variety of possible digraph families, and a version of the saddle-point method which can be systematically applied to the complex contour integrals appearing from the symbolic method. While the technically easiest model is the model of random multidigraphs, in which multiple edges are allowed, and where edge multiplicities are sampled independently according to a Poisson distribution with a fixed parameter p, we also show how to systematically approach the family of simple digraphs, where multiple edges are forbidden, and where 2-cycles are either allowed or not.
Our theoretical predictions are supported by numerical simulations, and we provide tables of numerical values for the integrals of Airy functions that appear in this study.
3. Exact enumeration of satisfiable 2-SAT formulae (with Élie de Panafieu and Vlady Ravelomanana)
Abstract
Abstract. 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 manipulations. To reflect the combinatorial specificities of the implication digraphs, we introduce a new kind of generating function, the Implication generating function, inspired by the Graphic generating function used in digraph enumeration. Using the underlying recurrences, we make accurate numerical predictions of the phase transition curve of the 2-SAT problem inside the critical window. We expect these exact formulae to be amenable to rigorous asymptotic analysis using complex analytic tools, leading to a more detailed picture of the 2-SAT phase transition in the future.
2. Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers (with Maciej Bendkowski and Olivier Bodini)
An extended version of the paper "Polynomial tuning of multiparametric combinatorial samplers" presented at ANALCO'18.
Abstract
Abstract. Combinatorial samplers are algorithmic schemes devised for the approximate-
and exact-size generation of large random combinatorial structures, such as
context-free words, various tree-like data structures, maps, tilings, RNA
molecules. They can be adapted to combinatorial specifications with additional
parameters, allowing for a more flexible control over the output profile of
parametrised combinatorial patterns. One can control, for instance, the number
of leaves, profile of node degrees in trees or the number of certain
sub-patterns in generated strings. However, such a flexible control requires an
additional and nontrivial tuning procedure.
Using techniques of convex optimisation, we present an efficient tuning
algorithm for multi-parametric combinatorial specifications. Our algorithm
works in polynomial time in the system description length, the number of tuning
parameters, the number of combinatorial classes in the specification, and the
logarithm of the total target size. We demonstrate the effectiveness of our
method on a series of practical examples, including rational, algebraic, and
so-called Pólya specifications. We show how our method can be adapted to a
broad range of less typical combinatorial constructions, including symmetric
polynomials, labelled sets and cycles with cardinality lower bounds, simple
increasing trees or substitutions. Finally, we discuss some practical aspects
of our prototype tuner implementation and provide its benchmark results.
1. Statistical properties of closed lambda-terms. (with Maciej Bendkowski and Olivier Bodini)
Electronic Journal of Combinatorics, 2019. [arXiv]
Abstract
Abstract. We present a quantitative, statistical analysis of random lambda terms in the de Bruijn notation. Following an analytic approach using multivariate generating functions, we investigate the distribution of various combinatorial parameters of random open and closed lambda terms, including the number of redexes, head abstractions, free variables or the de Bruijn index value profile. Moreover, we conduct an average-case complexity analysis of finding the leftmost-outermost redex in random lambda terms showing that it is on average constant. The main technical ingredient of our analysis is a novel method of dealing with combinatorial parameters inside certain infinite, algebraic systems of multivariate generating functions. Finally, we briefly discuss the random generation of lambda terms following a given skewed parameter distribution and provide empirical results regarding a series of more involved combinatorial parameters such as the number of open subterms and binding abstractions in closed lambda terms.
Conference Proceedings
Counting directed acyclic and elementary digraphs (with Élie de Panafieu) FPSAC 2020, as poster. [arXiv]
Abstract. Directed acyclic graphs (DAGs) can be characterised as directed graphs whose strongly connected components are isolated vertices. Using this restriction on the strong components, we discover that when , where is the number of directed edges, is the number of vertices, and , the asymptotic probability that a random digraph is acyclic is an explicit function , such that and .
When , the asymptotic behaviour changes, and the probability that a digraph is acyclic becomes , where is an explicit function of . Łuczak and Seierstad (2009, Random Structures & Algorithms, 35(3), 271--293) showed that, as , the strongly connected components of a random digraph with vertices and directed edges are, with high probability, only isolated vertices and cycles. We call such digraphs elementary digraphs. We express the probability that a random digraph is elementary as a function of . Those results are obtained using techniques from analytic combinatorics, developed in particular to study random graphs.
Symbolic method and directed graph enumeration (with Élie de Panafieu) EUROCOMB 2019. [arXiv]
Abstract. 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 directed acyclic graphs and of Liskovets, Robinson and Wright on the number of strongly connected directed graphs. We also recover Robinson's enumerative results on directed graphs where all strongly connected components belong to a given family.
Asymptotic distribution of parameters in random maps (with Olivier Bodini, Julien Courtiel, and Hsien-Kuei Hwang) AofA 2018. [arXiv]
Abstract. 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: vertices, leaves, loops, root edges, root isthmus, and root vertex degree. Each of these leads to a different limiting distribution, varying from (discrete) geometric and Poisson distributions to different continuous ones: Beta, normal, uniform, and an unusual distribution whose moments are characterised by a recursive triangular array.
Polynomial tuning of multiparametric combinatorial samplers (with Maciej Bendkowski and Olivier Bodini) ANALCO, 2018. [arXiv] [github]
Abstract. Boltzmann samplers and the recursive method are prominent algorithmic frameworks for the approximate-size and exact-size random generation of large combinatorial structures, such as maps, tilings, RNA sequences or various tree-like structures. In their multiparametric variants, these samplers allow to control the profile of expected values corresponding to multiple combinatorial parameters. One can control, for instance, the number of leaves, profile of node degrees in trees or the number of certain subpatterns in strings. However, such a flexible control requires an additional non-trivial tuning procedure. In this paper, we propose an efficient polynomial-time, with respect to the number of tuned parameters, tuning algorithm based on convex optimisation techniques. Finally, we illustrate the efficiency of our approach using several applications of rational, algebraic and Pólya structures including polyomino tilings with prescribed tile frequencies, planar trees with a given specific node degree distribution, and weighted partitions.
Shifting the phase transition threshold for random graphs using degree constraints (with Vlady Ravelomanana) LATIN, 2018. [arXiv]
Abstract. 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 vertices and edges can be either accelerated (e.g., for ) or postponed (e.g., ) compared to a classical Erdős–Rényi random graph with . In particular, we prove that the probability of graph being nonplanar and the probability of having a complex component, goes from to as passes . We investigate these probabilities and also different graph statistics inside the critical window of transition (diameter, longest path and circumference of a complex component).
Preprints
Asymptotics for graphically divergent series: dense digraphs and 2-SAT formulae (with Khaydar Nurligareev) Preprint, October 2023. [arXiv]
We propose a new method for obtaining complete asymptotic expansions in a systematic manner, which is suitable for counting sequences of various graph families in dense regime. The core idea is to encode the two-dimensional array of expansion coefficients into a special bivariate generating function, which we call a coefficient generating function. We show that coefficient generating functions possess certain general properties that make it possible to express asymptotics in a short closed form. Also, in most scenarios, we indicate a combinatorial meaning of the involved coefficients. Applications of our method include asymptotics of connected graphs, irreducible tournaments, strongly connected digraphs, satisfiable 2-SAT formulae and contradictory strongly connected implication digraphs. Moreover, due to its flexibility, the method allows to treat a wide range of structural variations, including fixing the numbers of connected, irreducible, strongly connected and contradictory components, having the variations on source-like, sink-like and isolated components, or adding weights and marking variables.
Structure and growth of -bonacci words (with Sergey Kirgizov) Preprint, October 2023. [arXiv]
Abstract. A Sturmian word of slope is the cutting sequence of a half-line . We establish a bijection between sequences of certain prefixes of the Sturmian word of slope , and the -decreasing words, which are binary words whose maximal factors of the form satisfy whenever . We also show that the number of -decreasing words of length grows as , where is the golden ratio, is equal to the tribonacci constant, and that the function is strictly increasing, discontinuous at every rational point, and exhibits a nice fractal structure related to the Stern—Brocot tree and Minkowski's question mark function.
The birth of the contradictory component in random 2-SAT Preprint, April 2019. [arXiv]
Abstract. 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 follows from the relation between these kernels and the complex component of a random graph in the subcritical phase. This partly settles the question about the structural similarity between the phase transitions in 2-SAT and random graphs. As a byproduct, we describe the technique that allows to obtain a full asymptotic expansion of the satisfiability in the subcritical phase. We also obtain the distribution of the number of contradictory variables and the structure of the spine in the subcritical phase.
Theses
An interdisciplinary image of Analytic Combinatorics. PhD Thesis, 2019. [hal] Thesis advisors: Olivier Bodini and Vlady Ravelomanana. Jury: Mireille Bousquet-Mélou, Éric Fusy, Andrea Sportiello, Brigitte Vallée. Referees: Éric Fusy, Valeriy Liskovets, Konstantinos Panagiotou.
Abstract. This thesis is devoted to the development of tools and the use of methods from Analytic Combinatorics, including exact and asymptotic enumeration, statistical properties of random objects, and random generation. The key ingredient is the multidisciplinarity of the domain, which is emphasised by using examples from computational logic, statistical mechanics, biology, mathematical statistics, networks and queueing theory.
Towards model selection for local log-density estimation. Fisher and Wilks-type theorems. Master Thesis, 2016. [arXiv] Thesis advisor: Vladimir Spokoiny.
Abstract. 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 estimation suggested by Clive Loader (1996) and extends the theoretical results to finite-sample framework with the help of machinery of Spokoiny (2012). The results include bias expression from "deterministic" counterpart and Fisher and Wilks-type theorems from "stochastic". We elaborate on bandwidth trade-off
with explicit constants at big O notation. Explicit expressions involve (i) true density function and (ii) model that is selected (dimension, bandwidth, kernel and basis, e.g. polynomial). Existing asymptotic properties directly follow from our results. From the expressions obtained it is possible to control "the curse of dimension" both from the side of log-density smoothness and the inner space dimension.