Asymptotics for graphically divergent series: dense digraphs and 2-SAT formulae
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913590494101504 |
|---|---|
| author | Dovgal, Sergey Nurligareev, Khaydar |
| author_facet | Dovgal, Sergey Nurligareev, Khaydar |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05282 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Asymptotics for graphically divergent series: dense digraphs and 2-SAT formulae Dovgal, Sergey Nurligareev, Khaydar Combinatorics 05A16 (Primary) 05A15, 05A10, 05C30, 05C80, 05C20, 60C05, 68Q87, 68R07 (Secondary) G.2.1; G.2.2; G.3 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. |
| title | Asymptotics for graphically divergent series: dense digraphs and 2-SAT formulae |
| topic | Combinatorics 05A16 (Primary) 05A15, 05A10, 05C30, 05C80, 05C20, 60C05, 68Q87, 68R07 (Secondary) G.2.1; G.2.2; G.3 |
| url | https://arxiv.org/abs/2310.05282 |