Loop clusters on complete graphs
Yves Le Jan · 2025
Read Loop clusters on complete graphs by Yves Le Jan (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-2504-16976.txt.
Introduction
Yves Le Jan, writing alone in 2025, studies the clusters formed by random loops sprinkled over a complete graph. On any graph, a Poisson ensemble of Markov loops, closed walks weighted by their transition steps, marks out occupied edges that split the graph into clusters. The paper first recalls the general machinery: conductances, a killing term, and a Green matrix that encodes how walks spread.
Against that backdrop, the probability that the loop partition is thinner than a named partition takes a simple closed form through those Green matrices, including versions restricted to a subset of vertices. An alternative construction builds the same clusters from primitive loops, those without a repeating period, chosen independently with matched probabilities. On the complete graph, where every vertex touches every other, the symmetry promises explicit results. The paper sets up the tools such results will need.
Catalog record
| CREATOR | Yves Le Jan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 13 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16976
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Loop clusters on complete graphs Yves Le Jan Abstract We investigate random partitions of complete graphs defined by Poissonian emsembles of Markov loops 0 0 footnotetext: Key words and phrases: Markov loops, complete graphs 0 0 footnotetext: AMS 2010 subject classification: 60C05, 60J27, 60G60. 1 Loop clusters Let us first review briefly a few general results about loop clusters defined on a general graph \mathcal{G}=(X,E) , equiped with a set of conductances C_{x,y} and a nonnegative killing function \kappa . This review is based on references [ 3 ] , [ 2 ] and [ 4 ] . Our setup allows to define a transition matrix P_{x,y}=\frac{C_{x,y}}{\lambda_{x}} , with \lambda_{x}=\sum_{y}C_{x,y}+\kappa_{x} and a measure \nu on discrete oriented loops (see section 2.1 in [ 4 ] ): the measure of a loop is given by the product of the transition matrix values of his edges divided by its multiplicity. Then, one defines for each positive \alpha , a Poisson process \mathcal{DL}_{\alpha} of intensity \alpha\nu . The size of a loop configuration (i.e. a multiset of discrete loops) is defined to be the sum the lengths of its loops. Occupied edges define a partition \mathcal{C}_{\alpha} of the graph into connected components, possibly including some isolated vertices. Alternatively, the partition \mathcal{C}_{\alpha} can be defined using a random set \mathcal{PL}_{\alpha} of primitive discrete loops (a discrete loop \xi is said to be primitive if it does not have a non-trivial period). A primitive loop \eta belongs to \mathcal{PL}_{\alpha} with probability 1-(1-\nu(\eta_{i}))^{\alpha} ( =\nu(\eta_{i}) if \alpha=1 ) and this happens independently for all primitive loops. These two constructions are in fact simply related. Any discrete loop \xi can be represented by some multiple of a primitive discrete loop we can denote by \pi\xi . Then, \mathcal{PL}_{\alpha} can be identified with \pi(\mathcal{DL}_{\alpha}) (See section 5.1 in [ 4 ] ). If we assume that the graph \mathcal{G} is finite, and that \kappa does not vanish everywhere, the Green matrix G is defined to be the inverse of \lambda_{x}\delta_{x,y}-C_{x,y} . Moreover, given any subset D of X , the Green matrix G^{D} is the inverse of the restriction of \lambda_{x}\delta_{x,y}-C_{x,y} to D\times D ( X is replaced by D and \kappa by \kappa+\sum_{y\in X-D}C_{x,y}). The probability that \mathcal{C}_{\alpha} is thinner ( \succeq ) than a given partition \pi has a simple expression in terms of the Green matrices (See [ 2 ] or section 5.3 in [ 4 ] ).: Proposition 1.1 Given a partition \pi=(B_{i})_{i\in I} of X , \Pd(\mathcal{C}_{\alpha}\succeq\pi)=\left(\frac{\prod_{i\in I}\det(G^{B_{i}})}{\det(G)}\right)^{\alpha}. (1) An explicit formula for \Pd(\mathcal{C}_{\alpha}=\pi) was derived from this proposition in [ 2 ] . Let us first introduce some notations. For a partition \pi , let |\pi| denote the number of non-empty blocks of \pi . For a subset A of X , let \pi_{|A} denote the restriction of \pi to A : \pi_{|A} is a partition of A , the blocks of which are the intersection of the blocks of \pi with A . Proposition 1.2 Let \pi be a partition of X with k non-empty blocks denoted by B_{1},\ldots,B_{k} . Then \Pd(\mathcal{C}_{\alpha}=\pi)=\sum_{\tilde{\pi}\succeq\pi}(-1)^{|\tilde{\pi}|-k}\prod_{i=1}^{k}(|\tilde{\pi}_{|B_{i}}|-1)!\Pd(\mathcal{C}_{\alpha}\succeq\tilde{\pi}). (2) 2 Clusters in the complete graph Let us consider the case of the complete graph K_{n} endowed with unit conductances and a constant killing factor \kappa . The expression of the Green matrix G is: \frac{1}{\kappa(n+\kappa)}(\kappa I+J) where J denotes the (n,n) matrix with all entries equal to 1 . Similarly, if |D|=d , the expression of the Green matrix G^{D} is: \frac{1}{(n-d+\kappa)(n+\kappa)}((n-d+\kappa)I_{D}+J_{D}) where I_{D} and J_{D} denote the restrictions of the (n,n) matrices I and J to D\times D . Moreover, it is easy to check that for any (m,m) square matrix M with diagonal entries equal to a+b and off diagonal entries equal to b , \det(M)=a^{m-1}(a+mb) . Hence we get the following: Lemma 2.1 \det(G)=\frac{1}{\kappa(n+\kappa)^{n-1}} and \det(G^{D}) = \frac{1}{(n-d+\kappa)(n+\kappa)^{d-1}} . Hence, by formula ( 1 ), if \pi is a partition of the set of vertices X with l blocks B_{1},\ldots,B_{l} then, \frac{\prod_{i}\det(G^{B_{i}})}{\det(G)}=(\frac{\kappa}{\kappa+n})\prod_{1\leq i\leq l}(1-\frac{|B_{i}|}{n+\kappa})^{-1} and \Pd(\mathcal{C}_{\alpha}\succeq\pi)=(\frac{\kappa}{\kappa+n})^{\alpha}\prod_{i=1}^{l}(1-\frac{|B_{i}|}{n+\kappa})^{-\alpha}. Let us note that (1-\frac{j}{n+\kappa})^{-\alpha} is the j -th moment m_{j}^{(\alpha)} of the random variable Y^{(\alpha)}=\exp(\frac{Z^{(\alpha)}}{n+\kappa}) where Z^{(\alpha)} denotes a Gamma (\alpha,1) -distributed random variable. In particular, for \alpha=1 , Y^{(1)} has density \un_{[1,\infty)}(n+\kappa)y^{-(n+\kappa+1)} . Thus, \displaystyle{\Pd(\mathcal{C}_{\alpha}\succeq\pi)=\frac{\prod_{i=1}^{k}m^{(\alpha)}_{\left|B_{i}\right|}}{m_{n}^{(\alpha)}}}. Equivalently, if D_{1},...,D_{k} are disjoint sets of vertices,,with |D_{i}|=d_{i} , \Pd(D_{1},...,D_{k}\text{ are isolated})=\Pd(\mathcal{C}_{\alpha}\succeq\{D_{1},...,D_{k},X-\bigcup_{1}^{k}D_{i}\})=\frac{\prod_{i=1}^{k}m^{(\alpha)}_{d_{i}}m_{n-\sum_{1}^{k}d_{i}}^{(\alpha)}}{m_{n}^{(\alpha)}}. In particular, given any k -tuple of vertices x_{1},...,x_{k} , \Pd(x_{1},...,x_{k}\text{ are isolated})=\frac{\kappa^{\alpha}}{(k+\kappa)^{\alpha}}(1-1/(n+\kappa))^{-k\alpha}. Denoting by I_{1} the set of isolated vertices, we can therefore compute the factorial moments of |I_{1}| : \Ed(|I_{1}|)(|I_{1}|-1)...(|I_{1}|-k+1)=n(n-1)...(n-k+1)\frac{\kappa^{\alpha}}{(k+\kappa)^{\alpha}}(1-1/(n+\kappa))^{-k\alpha}. (3) Let c_{n}^{(\alpha)} denote the n -th cumulant of Y^{(\alpha)} . Formula ( 2 ) and the expression of cumulants in terms of moments (see for example Section 3.3 in [ 1 ] , or formula (1.30) in [ 5 ] ) yield that: \Pd(\mathcal{C}_{\alpha}=\{X\})=\frac{c_{n}^{(\alpha)}}{m_{n}^{(\alpha)}}. (4) Given D any set of vertices, since the sets of loops contained in D and the sets of loops intersecting X-D are independent, the probability for D to be a connected cluster of \mathcal{C}_{\alpha} given that D is isolated is the probability that the cluster decomposition of D defined by the loops of \mathcal{DL}_{\alpha} carried by D is trivial. Replacing X by D and \kappa by n-d+\kappa in formula ( 4 ) entails that it equals \frac{c_{d}^{(\alpha)}}{m_{d}^{(\alpha)}} . More generally, given D_{1},...,D_{k} disjoint sets of vertices, since the sets of loops contained in each D_{i} and the set of loops intersecting X-\bigcup_{1}^{k}D_{i} are all independent, the probability for D_{1},...,D_{k} to be connected given that they are isolated is \prod_{1}^{k}\frac{c_{d_{i}}^{(\alpha)}}{m_{d_{i}}^{(\alpha)}} . Therefore, \Pd(D_{1},...,D_{k}\text{ are clusters of }(\mathcal{C}_{\alpha})=\frac{\prod_{i=1}^{k}c^{(\alpha)}_{d_{i}}m_{n-\sum_{1}^{k}d_{i}}^{(\alpha)}}{m_{n}^{(\alpha)}}=\prod_{i=1}^{k}c^{(\alpha)}_{d_{i}}\frac{\kappa^{\alpha}}{(\sum_{1}^{k}d_{i}+\kappa)^{\alpha}}. Denoting by I_{d} the set of \mathcal{C}_{\alpha} -clusters of size d , we can now compute the factorial moments of |I_{d}| : \Ed(|I_{d}|)...(|I_{d}|-k+1)={n\choose d}{n-d\choose d}...{n-kd+d\choose d}[c_{d}^{(\alpha})]^{k}\left(\frac{\kappa}{(kd+\kappa)}\right)^{\alpha}. (5) 3 Asymptotics Letting n increase to infinity, we get from formula ( 3 ) and from the expression of moments in terms of factorial moments using Stirling numbers that \Ed(|I_{1}|^{k})\sim n^{k}\left(\frac{\kappa}{k+\kappa}\right)^{\alpha}. Let us note that (\left(\frac{\kappa}{k+\kappa}\right)^{\alpha} is the k -th moment of the random variable R_{\alpha}=\exp(\frac{-Z_{\alpha}}{\kappa}) where Z_{\alpha} denotes a Gamma (\alpha,1) -distributed random variable. In particular, for \alpha=1 , R_{1} has density \un_{[0,1]}(\kappa)x^{\kappa-1} . Consequently: Proposition 3.1 The proportion |I_{1}|/n of isolated vertices converges in distribution towards R^{(\alpha)} . Similarly, we wish to get get from formula ( 5 ) asymptotics for the distribution of |I_{d}| . Lemma 3.1 As n increases to infinity, c_{d}^{(\alpha)} is equivalent to \alpha(d-1)!n^{-d} . Proof. This result is suggested by explicit calculations of c_{d}^{(\alpha)} for small d , but will be proved by considering the probability p_{C} for an isolated set of size d to be connected (as it is clear that \lim_{n\rightarrow\infty}m_{d}^{(\alpha)}=1 ). Firstly, we note that p_{C} is larger than the probability p_{-} that exactly one of the (d-1)! d -gons covering D belongs to \mathcal{DL}_{\alpha} . As P_{x,y}=\frac{1}{n+\kappa-1} , the \nu - measure of a d -gon equals u_{d}=(n+\kappa-1)^{-d} and p_{-}=(d-1)!\alpha u_{d}e^{-d\alpha u_{d}} It is equivalent to \alpha(d-1)!n^{-d} as n\rightarrow\infty . To get an upper bound, let us first assume that \alpha\geq 1 . p_{C} is smaller than p_{-} + the probability p_{>} that the total size M of the loops of \mathcal{DL}_{\alpha} included in D is larger than (2d+1)\alpha + the sum, on all loop configurations included in D with size at least d+1 and at