Local limits of determinantal processes
Asaf Nachmias, Yuval Peled · 2025
Read Local limits of determinantal processes by Asaf Nachmias, Yuval Peled (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-2510-19563.txt.
Introduction
Asaf Nachmias and Yuval Peled determine the local limit of a broad family of determinantal processes. These random processes arise from orthogonal projections and include uniform spanning trees, determinantal hypertrees, and related structures in combinatorics. The authors look at projections onto row spaces of signed adjacency matrices of certain bipartite graphs with no four-cycles.
As the graph grows, one side's degree rises without bound while the other side's stays fixed. Nachmias and Peled show the local limit is a variant of a branching process with Poisson-distributed offspring, conditioned to survive forever. The single result covers spanning trees, hyperforests, discrete Grassmannians, and incidence matroids whenever their degree tends to infinity.
Catalog record
| CREATOR | Asaf Nachmias, Yuval Peled |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-19563
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Local limits of determinantal processes Asaf Nachmias, Yuval Peled Abstract Let H n H_{n} be the row space of a signed adjacency matrix of a C 4 C_{4} -free bipartite bi-regular graph in which one part has degree d ( n ) → ∞ d(n)\to\infty and the other part has degree k + 1 k+1 where k ≥ 1 k\geq 1 is a fixed integer. We show that the local limit as n → ∞ n\to\infty of the determinantal process corresponding to the orthogonal projection on H n H_{n} is a variant of a Poisson ( k ) (k) branching process conditioned to survive. This setup covers a wide class of determinantal processes such as uniform spanning trees, Kalai’s determinantal hypertrees, hyperforests in regular cell complexes, discrete Grassmanians, incidence matroids and more, as long as their degree tends to ∞ \infty . 1 Introduction We study the local limits of determinantal processes. To do this one must have an adjacency relation between the process’ elements which general determinantal processes do not posses. Hence we restrict our setting to processes which naturally have such a structure. This restricted setting may seem unfamiliar at a first glance, but in fact it includes many well studied examples such as the uniform spanning tree, Kalai’s determinantal hypertrees [ 10 ] and many more (see Section 1.2 ). In this setting, the determinantal process is a probability measure on subsets of cardinality r of some finite ground set U . We think of U as the right sided vertex subset of a bipartite graph G=(V,U,E) where V\uplus U are the left and right vertex subsets, respectively, and E is the edge set. For a random sample \mathcal{T}\subset U drawn according to this measure, we study the induced subgraph G[\mathcal{T}] consisting of \mathcal{T} together with all its neighbors in G . Assuming that G is C_{4} -free and (d,k+1) -bi-regular with fixed k and d\to\infty , we prove that the rooted random graph (G[\mathcal{T}],o) , where o\in V is chosen uniformly at random, converges in distribution with respect to the local topology of rooted graphs to a variant of a Poisson (k) branching process, which we denote by \mathbb{T}_{k} . Notably, the limit depends only on k . Our main result ( Theorem 1.1 ) recovers the main result of [ 22 ] regarding the local limit uniform spanning trees of d -regular graphs and significantly extends the result in [ 15 ] on the local limit of Kalai’s determinantal hypertrees to include determinantal hyperforests of any high-degree cell complex. More importantly, we provide a unified linear algebraic approach to proving such local limits which include a very wide class of determinantal processes, see Section 1.2 below for examples. 1.1 Setup and main result Suppose that G_{n}=(V_{n},U_{n},E_{n}) is a sequence of simple bipartite graphs where V_{n}\uplus U_{n} is the vertex set and E_{n} is the edge set. For notational convenience we frequently drop the subscript n and denote G=(V,U,E) instead of G_{n}=(V_{n},U_{n},E_{n}) . We assume that |V|=n and |U|=m and that G is C_{4} -free (that is, any two vertices G have at most one common neighbor) and that it is a (d,k+1) -bi-regular graph, i.e., the degree of v\in V is d and the degree of u\in U is k+1 . So m=nd/(k+1) . We assume that k\geq 1 is a fixed integer and that d\to\infty as n\to\infty Let B be a n\times m signed adjacency matrix of G , i.e., B_{u,v}\in\{1,-1\} if uv\in E and B_{u,v}=0 otherwise. Denote r=\operatorname{rank}(B)\leq\min(n,m) . Let H\subset\mathbb{R}^{m} be the row space of B and denote by P_{H}:\mathbb{R}^{m}\to H the orthogonal projection operator onto H which we treat as an m\times m matrix represented in the standard basis of \mathbb{R}^{m} . Given a subset \mathcal{T}\subset U , we follow Lyons’ notation [ 12 ] , and denote P_{H}\res\mathcal{T} for the submatrix of P_{H} whose rows and columns are indexed by \mathcal{T} . The determinantal process associated with H is a probability measure \mathbb{P}^{H} on subsets \mathcal{T}\subset U of size |\mathcal{T}|=r given by (1.1) \displaystyle\mathbb{P}^{H}(\mathcal{T})=\det(P_{H}\res\mathcal{T})\,. To see that ( 1.1 ) defines a probability measure let \{\psi_{1},\ldots,\psi_{r}\} be an orthonormal basis of H viewed as row vectors and let C=(\psi_{1},\ldots,\psi_{r}) be an r\times m matrix; then applying Cauchy-Binet on the left hand side of the equality \det(CC^{T})=1 yields that \sum_{|\mathcal{T}|=r}\mathbb{P}^{H}(\mathcal{T})=1 . Also, the r\times r matrix P_{H}\res\mathcal{T} is nonsingular only when the columns of B indexed by \mathcal{T} span an r -dimensional space. Hence, the measure \mathbb{P}^{H} is supported on subsets \mathcal{T}\subset U such that these columns form a basis of the column space of B . In particular, if \mathcal{T}\subset U is such that \mathbb{P}^{H}(\mathcal{T})>0 , then every v\in V has a neighbor in \mathcal{T} (in other words, such \mathcal{T} must be spanning ). Given a subset \mathcal{T}\subset U we denote by G[\mathcal{T}] the subgraph of G induced by the vertices N_{G}(\mathcal{T})\cup\mathcal{T} , where N_{G}(\mathcal{T}) is the subset of V of neighbors of \mathcal{T} in G . Our goal is to study the local limit (see below) of G[\mathcal{T}] as n\to\infty . The limiting object \mathbb{T}_{k} , first studied by Linial and the second author [ 11 ] , is a variant of a Poisson (k) branching process. Formally \mathbb{T}_{k} is an infinite random rooted tree that is drawn according multi type branching process with 4 types: \mathfrak{a} -even, \mathfrak{a} -odd, \mathfrak{b} -even and \mathfrak{b} -odd. The symbol odd/even only represents the parity of the distance from the root (intuitively, the even vertices correspond to V and the odd to U ). The root \rho is of type \mathfrak{a} -even, and the distribution of the number of progeny and their types for a given type is given by the following rules, where all the Poisson (k) random variables below are independent: • A particle of type \mathfrak{a} -even has 1 child of type \mathfrak{a} -odd and Poisson (k) children of type \mathfrak{b} -odd. • A particle of type \mathfrak{b} -even has Poisson (k) children of type \mathfrak{b} -odd. • A particle of type \mathfrak{a} -odd has k children all of them of type \mathfrak{a} -even. • A particle of type \mathfrak{b} -odd has k-1 children of type \mathfrak{a} -even and 1 child of type \mathfrak{b} -even. Theorem 1.1 . Let k\geq 1 be an integer, d(n)\to\infty an integer sequence, G_{n}=(V_{n},U_{n},E_{n}) a sequence of simple C_{4} -free bipartite graphs that are (d(n),k+1) bi-regular, B_{n} a |V_{n}|\times|U_{n}| signed adjacency matrix of G_{n} , \mathcal{T}_{n} be drawn according to the determinantal probability measure ( 1.1 ) associated with the row space of B_{n} , and o_{n}\in V_{n} is chosen uniformly at random independently. Then the rooted graphs (G[\mathcal{T}_{n}],o_{n}) converge in distribution with respect to the local topology to (\mathbb{T}_{k},\rho) . The only notion left to recall in order to parse Theorem 1.1 is the local rooted graph topology , first introduced in the influential paper of Benjamini and Schramm [ 2 ] . Let \mathcal{G}_{\bullet} be the set of all locally finite rooted graphs (G,o) viewed up to root preserving graph isomorphism. Given a rooted graph (G,o)\in\mathcal{G}_{\bullet} and an integer r\geq 0 we write B_{G}(o,r) for the induced graph of G on the vertices of graph distance at most r from o