Résumé : We propose a new method for obtaining the coefficients of complete asymptotic expansions in a systematic manner, which is suitable for various families of graphs in dense regime. The core idea is to introduce a new type of (bivariate) generating series for the expansion coefficients, which we call a coefficient generating function. We show that the coefficient generating functions possess certain general properties that make it possible to express the asymptotics in a short closed form and give a combinatorial meaning to their 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, using marking variables, we obtain asymptotics of the above families with a fixed number of connected, irreducible, strongly connected and contradictory components, respectively. This is joint work with Sergey Dovgal.

 [Slides.pdf] [vidéo]

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr