Asymptotic number of edge-colored regular graphs
Michael Borinsky and Chiara Meroni and Maximilian Wiesmann · 2026
Read Asymptotic number of edge-colored regular graphs by Michael Borinsky and Chiara Meroni and Maximilian Wiesmann (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18994.txt.
Introduction
Michael Borinsky, Chiara Meroni, and Maximilian Wiesmann count colored regular graphs as they grow huge. A regular graph gives each node the same number of links, and colors on the edges add a further rule. The team proves a formula for how many such graphs exist when the count grows large.
The formula hangs on special points of a polynomial that encodes what may sit at each node. As a use case, they work out how many proper edge colorings a large random regular graph should have on average. Counts like this guide both combinatorics and models of random networks.
Catalog record
| CREATOR | Michael Borinsky and Chiara Meroni and Maximilian Wiesmann |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-18994
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymptotic number of edge-colored regular graphs Michael Borinsky and Chiara Meroni and Maximilian Wiesmann Abstract . We prove a formula for the asymptotic number of edge-colored regular graphs with a prescribed set of allowed vertex-incidence structures. The formula depends on specific critical points of a polynomial encoding the vertex-incidences. As an application, we compute the expected number of proper c c -edge-colorings of a large random k k -regular graph. 1. Introduction In this paper we study the asymptotic number of edge-colored regular graphs with a prescribed set of possible vertex-incidence structures. The asymptotic enumeration of regular graphs is a topic with a long history, see for instance [ BC78 , Bol82 , MW91 ] , and more recently [ LW24 ] . Since Lovász and co-authors introduced graphons [ Lov12 ] , large deviation principles have given rise to asymptotic enumeration results, see, e.g., [ Cha17 , §6] . This framework also naturally allows for edge-colors [ Lov12 , §23.2] . Our setup differs from most of the previously mentioned works in at least three respects. First, we impose precise constraints on the allowed vertex-incidence structures. In particular, this enables us to derive asymptotic counts for proper edge-colorings in Section 4 . Second, we allow graphs to have self-loops and multiple edges. Sometimes such graphs are also called multigraphs in the literature. Third, we weight graphs by the inverse cardinality of their automorphism group, which is equivalent to counting half-edge labeled graphs. Such weights arise naturally, for instance, in the context of Polyá enumeration theory [ Pól37 ] , the theory of combinatorial species [ Joy81 ] , Feynman diagram expansions in quantum field theory [ BIZ80 ] , geometric group theory [ CV86 ] , and enumerative geometry [ Kon92 ] . Further, such weights appear as compensation factors in classical random graphs studies (see, e.g., [ Jan+93 ] ). Beyond these structural differences, the novelty of our approach lies in the application of analytic combinatorial techniques to regular graph counting. The analytic combinatorics framework, popularized by Flajolet and Sedgewick [ FS09 ] , has been remarkably successful in providing precise asymptotic estimates for various discrete structures, most notably in the analysis of large-scale data structures and the distribution of patterns in random mappings. In this paper, we demonstrate that the asymptotic enumeration of edge-colored regular graphs is equivalent to the analytic problem of locating the critical points of a specific polynomial. v_{6} v_{1} v_{2} v_{3} v_{4} v_{5} Figure 1. An edge-colored 5 -regular graph, element of \mathcal{G}_{5}^{3}(6) . Let \mathcal{G}_{k}^{c}(n) be the set of isomorphism classes of k -regular graphs with n vertices, whose edges can have c different colors. We allow graphs to have multiple edges and self-loops. Each vertex v of such a graph has a multidegree \deg(v)=(w_{1},\ldots,w_{c})\in\mathbb{Z}_{\geq 0}^{c} , where w_{i} denotes the number of edges of color i incident to v . A self-loop contributes two incidences at a single vertex. The regularity assumption implies that \sum_{i=1}^{c}w_{i}=k . Let \mathcal{C}_{k}^{c} denote the set of integer compositions of k into c (possibly zero) parts. Each element of \mathcal{C}_{k}^{c} can occur as the multidegree of a vertex. Let \{\Lambda_{\bm{w}}\}_{\bm{w}\in\mathcal{C}_{k}^{c}} be a family of parameters indexed by these compositions \bm{w}=(w_{1},\ldots,w_{c})\in\mathcal{C}_{k}^{c} . The \Lambda_{\bm{w}} serve as vertex markings. Figure 1 shows a (k\!=\!5) -regular graph with six vertices and c=3 edge colors: green, red, yellow. With respect to this ordering, the vertex multidegrees are (1,2,2) for v_{1},v_{3},v_{4} , (1,1,3) for v_{2},v_{5} , and (5,0,0) for v_{6} . The main result of this article, Theorem 1.1 , is an asymptotic formula for the weighted sum, (1) \displaystyle A(n)=\sum_{G\in\mathcal{G}_{k}^{c}(n)}\frac{1}{|\Aut(G)|}\prod_{v\in V_{G}}\Lambda_{\deg(v)}\,, where \Aut(G) is the group of automorphisms of a labeled graph \Gamma representing G as defined below. Throughout, we use the multi-index notation: bold symbols typically denote c -tuples, as in \bm{w}=(w_{1},\dots,w_{c}) . The multi-index factorial is \bm{w}!=w_{1}!\cdots w_{c}! , while \bm{x}^{\bm{w}} is shorthand notation for x_{1}^{w_{1}}\cdots x_{c}^{w_{c}} . Moreover, we use |\bm{w}|=w_{1}+\dots+w_{c} . We define a polynomial g\in\mathbb{R}[x_{1},\ldots,x_{c}] storing the parameters \Lambda_{\bm{w}} by (2) g(x_{1},\ldots,x_{c})=-\sum_{i=1}^{c}\frac{x_{i}^{2}}{2}+\sum_{\bm{w}\in\mathcal{C}_{k}^{c}}\Lambda_{\bm{w}}\frac{\bm{x}^{\bm{w}}}{\bm{w}!}\,. Let \crit^{*}(g) be the set of critical points of g lying in the complex cone over the sphere S^{c-1} , \crit^{*}(g)=\left\{\bm{z}\in\mathbb{C}^{c}\,:\,\frac{\partial g}{\partial x_{1}}(\bm{z})=\ldots=\frac{\partial g}{\partial x_{c}}(\bm{z})=0\text{ and }\bm{z}=\tau\cdot\bm{x}\text{ for }\tau\in\mathbb{C}\setminus\{0\}\text{ and }\bm{x}\in S^{c-1}\right\}. Among these, let \Psi=\argmin_{\bm{z}=\tau\cdot\bm{x}\in\crit^{*}(g)}|\tau| be the subset of critical points of minimal distance to the origin. Moreover, let \Hess g be the Hessian of g which is the symmetric matrix formed by its second partial derivatives. Theorem 1.1 . If all critical points \bm{z}\in\Psi are non-degenerate, i.e. \det(\Hess g(\bm{z}))\neq 0 , then (3) A(n)\sim\frac{1}{2\pi}(\ell-1)!\sum_{\bm{z}\in\Psi}\frac{(-g(\bm{z}))^{-\ell}}{\sqrt{(-1)^{c-1}\det(\Hess g(\bm{z}))}}\quad\text{ for large integers }\ell=n\left(\frac{k}{2}-1\right). This result generalizes [ BMW24 , Theorem 5.3] , which treats the bicolored case c=2 . The key ingredient in the proof of Theorem 1.1 is an expression of A(n) as a multivariate exponential integral (Lemma 3.1 ) which is then amenable to a saddle point analysis in the spirit of analytic combinatorics (Proposition 3.3 ). Let {E}^{c}_{k}(n) be the average number of proper c -edge-colorings of all k -regular vertex-labeled graphs with multiple edges but no self-loops and n vertices, or equivalently the expected number of proper c -edge-colorings of random k -regular n -vertex labeled multigraphs without self-loops. Here, random means with respect to the uniform distribution on the set of such vertex-labeled graphs. As an example application of Theorem 1.1 , we combine it with a classical result on the asymptotic number of regular (multi)graphs [ BC78 ] to obtain an expression for {E}^{c}_{k}(n) when n is large while k and c remain fixed. Theorem 1.2 . Let k\geq 3 and assume \ell=n\left(\tfrac{k}{2}-1\right)\in\mathbb{Z}_{>0} . Then, for large n\in\mathbb{Z}_{>0} , we have {E}^{c}_{k}(n)\sim\left\{\begin{array}[]{ll}2^{(k-1)/2}\left(\frac{k!}{\sqrt{k}^{k}}\right)^{n}\exp\left(-\frac{1}{4}(k^{2}-4k+3)\right)&\text{ if }c=k,\text{ and }n\text{ even},\\ \left(\frac{k-1}{c-1}+1\right)^{(1-c)/2}\left(k!\binom{c}{k}\right)^{n}c^{-\frac{nk}{2}}\exp\left(-\frac{1}{4}(k^{2}-4k+3)\right)&\text{ if }c>k,\\ 0&\text{ else.}\end{array}\right. Outline. The paper is structured as follows. In Section 2 , we give a precise definition of the graphs considered and derive a counting formula with respect to the vertex multidegrees in Proposition 2.3 . Section 3 is devoted to the proof of the asymptotic behavior of the (weighted) number of such edge-colored graphs, culminating in the proof of Theorem 1.1 . Finally, Section 4 discusses an application of our theorem to count the average number of proper edge-colorings and proves Theorem 1.2 . 2. Edge-colored half-edge labeled graphs In this section, we explain the framework of half-edge labeled graphs. For the case of bicolored graphs, this has appeared in [ BMW24 , §3] , the multicolored case has been described in [ Wie26 , §2] . We restate it here to make the paper self-contained. Given a finite set H of labels, an H - half-edge labeled graph is a pair (V,E) where V and E are set-partitions of H with the constraint that E has only blocks of size two. Interpreting each block of V as a vertex gives rise to a graph that can have multiple edges and self-loops. Remark 2.1 . In classical graph theory, a (simple) graph is defined as a set of vertices V and a set of two-element subsets E\subset V , which inherently makes it a simplicial complex . However, applications in topology and physics often require a more flexible definition that allows the graph to be a general finite, at most one-dimensional CW complex (see, e.g., [ BIZ80