2023/10/08 by Sergey Dovgal, Dovgal, Sergey, Khaydar Nurligareev +1 · 1 citation
Chemistry · Computer Science · #History and advancements in chemistry #Topological and Geometric Data Analysis #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.2310.05282
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, 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, as well as source-like, sink-like and isolated ones, or adding weights and marking variables.