Universality of the matching number in percolated regular graphs
Sahar Diskin, Mihyun Kang, Lyuben Lichev · 2025
Read Universality of the matching number in percolated regular graphs by Sahar Diskin, Mihyun Kang, Lyuben Lichev (2025) 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-2503-11242.txt.
Introduction
Sahar Diskin, Mihyun Kang, and Lyuben Lichev prove a shared limit law for matched pairs in random graphs in a 2025 paper. The graphs start as regular networks where each node has the same degree. Edges are then kept at random with a small chance. The team study how many disjoint edge pairs, or matchings, survive.
They prove a tight local limit for the thinned graphs. That limit joins with known results from other authors. It shows the scaled matching count matches that of a classic random graph. The match holds even as the base degree grows without bound. The result is a case of universality in random graph theory. One simple model captures many distinct starting graphs.
Catalog record
| CREATOR | Sahar Diskin, Mihyun Kang, Lyuben Lichev |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-11242
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Universality of the matching number in percolated regular graphs Sahar Diskin, Mihyun Kang, Lyuben Lichev Abstract Fix a sequence of d d -regular graphs ( G d ) d ∈ ℕ (G_{d})_{d\in\mathbb{N}} and denote by G d , p G_{d,p} the graph obtained from G d G_{d} after edge-percolation with probability p = c / d p=c/d , for a constant c > 0 c>0 . We prove a quantitative local convergence of ( G d , p ) d ∈ ℕ (G_{d,p})_{d\in\mathbb{N}} . In combination with results of Bordenave, Lelarge and Salez, it implies that the rescaled matching number of G d , p G_{d,p} is asymptotically equivalent to that of the binomial random graph G ( n , c / n ) G(n,c/n) . 1 Introduction A matching in a graph G is a collection of pairwise non-adjacent edges M\subseteq E(G) . Denote by \mathcal{M}(G) the set of all matchings in G , and define the matching number of G by \displaystyle\nu(G)\penalty\ :=\penalty\ \max_{M\in\mathcal{M}(G)}|M|. A graph is said to have a perfect matching if it has a matching M incident to all vertices of G ; equivalently, when 2\nu(G)=|V(G)| . The binomial random graph G(n,p) is formed by retaining each edge of the complete graph on n vertices K_{n} independently with probability p . When (n-1)p=c for some constant c>0 , G(n,p) typically contains isolated vertices, and thus cannot have a perfect matching. Nonetheless, determining the asymptotic value of the rescaled matching number \nu(G(n,p))/n is not a trivial task. For a constant c>0 , let y=y(c) be the smallest solution in (0,1) of \displaystyle y\penalty\ =\penalty\ \exp\left(-c\exp(-cy)\right), (1) and consider a function \displaystyle F(c)\penalty\ :=\penalty\ 1-\frac{y+\exp(-cy)+cy\exp(-cy)}{2}. (2) We note that \lim_{c\to\infty}F(c)=1/2 . In a seminal work, Karp and Sipser [ 14 ] showed that \displaystyle\frac{\nu\left(G(n,c/n)\right)}{n}\quad\xrightarrow[n\to\infty]{}\quad(1+o(1))\penalty\ F(c), where the convergence holds in probability. At the heart of the proof of this result lies the so-called Karp-Sipser algorithm . It is based on the observation that any vertex of degree one, called a leaf, participates in at least one maximum matching. The algorithm applies an iterative deletion process of leaves and their unique neighbours, ending up with the Karp-Sipser core of the graph. The careful analysis of the Karp-Sipser algorithm provides precise asymptotic expressions for the rescaled matching number and the rank of the adjacency matrix of random graphs [ 1 , 2 , 4 , 5 , 6 , 7 , 13 , 15 ] . The binomial random graph G(n,p) is one instance of edge-percolation . Given a host graph G and a probability p\in[0,1] , we form the random subgraph G_{p}\subseteq G by retaining each edge of G independently and with probability p . (In particular, G(n,p) is obtained by percolating the edges of the complete graph K_{n} with probability p .) Another well-studied instance of edge-percolation is the percolated hypercube Q^{d}_{p} . The d -dimensional binary hypercube Q^{d} is the graph with vertex set \{0,1\}^{d} where uv\in E(Q^{d}) if and only if u and v differ in a single coordinate. Similarly to the binomial random graph, in the p -percolated hypercube, a giant component suddenly arises around the point p=1/d (see [ 12 , Chapter 13] ). In this note, we extend this analogy to the matching number of Q^{d}_{p} . A simple argument shows that \nu(Q^{d}_{c/d})/2^{d} tends to 1/2 as c tends to infinity (see [ 10 , Theorem 1] ). Yet, obtaining a precise result similar to that of Karp and Sipser [ 14 ] is not immediate: indeed, in their proof, the underlying analysis based on differential equations uses the homogeneity of the complete graph. In particular, the high-dimensional lattice-like geometry of Q^{d} invalidates this approach. Our main result establishes an analogue of the Karp-Sipser result for the percolated d -dimensional hypercube and, in fact, for any percolated d -regular graph with growing degree. Theorem 1.1 . Fix a constant c>0 and a sequence of d -regular graphs (G_{d})_{d\in\mathbb{N}} . Let p=p(d)=c/d . Then, \displaystyle{\frac{\nu\left((G_{d})_{p}\right)}{|V(G_{d})|}}\quad\xrightarrow[d\to\infty]{}\quad F(c)\hskip 43.05542pt\textit{in probability,} where F(c) is the same as in ( 2 ). The main part of the proof of Theorem 1.1 is based on showing that percolated regular graphs with growing degree converge locally in probability to a Galton-Watson branching process with offspring distribution \mathrm{Po}(c) (see Theorem 3.1 ) which, together with a result of Bordenave, Lelarge, and Salez [ 3 ] (Theorem 3.7 ), implies Theorem 1.1 . Theorem 1.1 contributes to an ongoing line of research, dedicated to the study of universality of binomial random graphs. Previous research has mainly studied the typical emergence of the giant component, its uniqueness, and asymptotic properties [ 8 , 9 , 11 , 17 ] . One significant feature distinguishing the above setting from our analysis of the matching number is that the minimal assumptions of regularity and growing degree in Theorem 1.1 are insufficient to uniquely identify the size of the giant component. For example, no giant component can appear as a subgraph of a disjoint union of cliques of order d+1 . In fact, the emergence of a giant component – and the universality of this phenomenon – are tightly connected to the expansion properties of the host graph. In contrast, our results show that the universality class for the matching number is much broader and contains all regular graphs of growing degree. Finally, note that the assumption that d is growing is necessary for our result to hold in such generality, as percolated regular graphs of bounded degree have a different local limit. This note is structured as follows. In Section 2 , we introduce some notation and terminology. In Section 3 , we prove a quantitative strengthening of Theorem 1.1 . Finally, in Section 4 , we briefly discuss extensions of Theorem 1.1 to even more general settings. 2 Notation and terminology In this note, \mathbb{N} denotes the set of positive integers. For 0<a<b , we write [a,b]=\{a,a+1,\ldots,b\} instead of \{a,a+1,\ldots,b\}\cap\mathbb{N} for brevity, and we also write [k]=\{1,2,\ldots,k\} for all k\in\mathbb{N} . All logarithms in this paper have base \mathrm{e} . Given a graph G and a set U\subseteq V(G) , we denote by \Delta(G) the maximum degree of G and by G[U] the subgraph of G induced by U . Let us further recall several variants of the notion of local convergence of a sequence of graphs. For a more detailed account on the topic, see [ 19 ] and Sections 2.3 and 2.4 in [ 21 ] . Given a graph H , a vertex v in H and an integer r\geq 0 , the r -th (closed) neighbourhood of v in G , denoted N^{r}_{H}[v] , is the set of vertices at (graph-)distance at most r from v in H . Moreover, the graph induced by these vertices is called the ball with radius r around v in H and denoted by B^{r}_{H}[v] . We often see B^{r}_{H}[v] as a graph rooted at v . Given a graph H and a vertex v , we denote by C_{H}(v) the connected component of H containing v . Then, with a slight abuse of notation, we think of the rooted graph (H,v) as the rooted (connected) graph (C_{H}(v),v) . We can then