Abstract:In this paper, we study the structure of the complete asymptotic expansion of the probability that a large combinatorial object is connected or consists of a given number of connected components. For rapidly growing labeled families of structures, the coefficients involved in these expansions are possibly negative integers. Using species theory, we interpret these coefficients as the difference between the counting sequences of two derivative species of structures. In particular, we show that this difference can be viewed as the counting sequence of the virtual species obtained with the help of an "anti-$\mathrm{SEQ}$" operator applied to the initial family of structures. Applications include $P$-angulated discrete surfaces, quadratic square-tiled surfaces, and non-orientable graph encoded manifolds, which were not reachable with our previous methods.
Moving on to the weighted species, we establish the whole structure of the asymptotic expansion of the probability that a graph is connected in the Erdős-Rényi model $G(n,p)$. Here, the asymptotic coefficients are polynomials in $\frac{p}{1-p}$ and can be described both in terms of simple graphs and irreducible tournaments with ties. We also provide general asymptotic results for sequence and cycle decomposition, as well as the complete asymptotic expansion of the probability that a random labeled tournament with ties is irreducible.
| Comments: | 35 pages, 2 figures, 4 tables |
| Subjects: | Combinatorics (math.CO) |
| Cite as: | arXiv:2605.25065 [math.CO] |
| (or arXiv:2605.25065v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25065 arXiv-issued DOI via DataCite (pending registration) |
From: Khaydar Nurligareev [view email]
[v1]
Sun, 24 May 2026 13:21:18 UTC (46 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。