Source author record

Christina Goldschmidt

Christina Goldschmidt appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.PR math.CO cond-mat.stat-mech math-ph math.MP

Catalog footprint

What is connected

9works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Moderate deviations of subgraph counts in the Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$

The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the Erdős-Rényi random graph $G(n,m)$. Our approach is based on applying Freedman's inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related $G(n,p)$ model.

preprint2020arXiv

Stable graphs: distributions and line-breaking construction

For $α\in (1,2]$, the $α$-stable graph arises as the universal scaling limit of critical random graphs with i.i.d. degrees having a given $α$-dependent power-law tail behavior. It consists of a sequence of compact measured metric spaces (the limiting connected components), each of which is tree-like, in the sense that it consists of an $\mathbb R$-tree with finitely many vertex-identifications (which create cycles). Indeed, given their masses and numbers of vertex-identifications, these components are independent and may be constructed from a spanning $\mathbb R$-tree, which is a biased version of the $α$-stable tree, with a certain number of leaves glued along their paths to the root. In this paper we investigate the geometric properties of such a component with given mass and number of vertex-identifications. We (1) obtain the distribution of its kernel and more generally of its discrete finite-dimensional marginals; we will observe that these distributions are related to the distributions of some configuration models (2) determine the distribution of the $α$-stable graph as a collection of $α$-stable trees glued onto its kernel and (3) present a line-breaking construction, in the same spirit as Aldous' line-breaking construction of the Brownian continuum random tree.

preprint2017arXiv

The spread of fire on a random multigraph

We study a model for the destruction of a random network by fire. Suppose that we are given a multigraph of minimum degree at least 2 having real-valued edge-lengths. We pick a uniform point from along the length and set it alight; the edges of the multigraph burn at speed 1. If the fire reaches a vertex of degree 2, the fire gets directly passed on to the neighbouring edge; a vertex of degree at least 3, however, passes the fire either to all of its neighbours or none, each with probability $1/2$. If the fire goes out before the whole network is burnt, we again set fire to a uniform point. We are interested in the number of fires which must be set in order to burn the whole network, and the number of points which are burnt from two different directions. We analyse these quantities for a random multigraph having $n$ vertices of degree 3 and $α(n)$ vertices of degree 4, where $α(n)/n \to 0$ as $n \to \infty$, with i.i.d. standard exponential edge-lengths. Depending on whether $α(n) \gg \sqrt{n}$ or $α(n)=O(\sqrt{n})$, we prove that as $n \to \infty$ these quantities converge jointly in distribution when suitably rescaled to either a pair of constants or to (complicated) functionals of Brownian motion. We use our analysis of this model to make progress towards a conjecture of Aronson, Frieze and Pittel concerning the number of vertices which remain unmatched when we use the Karp-Sipser algorithm to find a matching on the Erdős-Rényi random graph.

preprint2016arXiv

Behavior near the extinction time in self-similar fragmentations II: Finite dislocation measures

We study a Markovian model for the random fragmentation of an object. At each time, the state consists of a collection of blocks. Each block waits an exponential amount of time with parameter given by its size to some power $α$, independently of the other blocks. Every block then splits randomly into sub-blocks whose relative sizes are distributed according to the so-called dislocation measure. We focus here on the case where $α<0$. In this case, small blocks split intensively, and so the whole state is reduced to "dust" in a finite time, almost surely (we call this the extinction time). In this paper, we investigate how the fragmentation process behaves as it approaches its extinction time. In particular, we prove a scaling limit for the block sizes which, as a direct consequence, gives us an expression for an invariant measure for the fragmentation process. In an earlier paper [Ann. Inst. Henri Poincaré Probab. Stat. 46 (2010) 338-368], we considered the same problem for another family of fragmentation processes, the so-called stable fragmentations. The results here are similar, but we emphasize that the methods used to prove them are different. Our approach in the present paper is based on Markov renewal theory and involves a somewhat unusual "spine" decomposition for the fragmentation, which may be of independent interest.

preprint2016arXiv

Inverting the cut-tree transform

We consider fragmentations of an R-tree $T$ driven by cuts arriving according to a Poisson process on $T \times [0, \infty)$, where the first co-ordinate specifies the location of the cut and the second the time at which it occurs. The genealogy of such a fragmentation is encoded by the so-called cut-tree, which was introduced by Bertoin and Miermont for a fragmentation of the Brownian continuum random tree. The cut-tree was generalised by Dieuleveut to a fragmentation of the $α$-stable trees, $α\in (1, 2)$, and by Broutin and Wang to the inhomogeneous continuum random trees of Aldous and Pitman. Remarkably, in all of these cases, the law of the cut-tree is the same as that of the original R-tree. In this paper, we develop a clean general framework for the study of cut-trees of R-trees. We then focus particularly on the problem of reconstruction: how to recover the original R-tree from its cut-tree. This has been studied in the setting of the Brownian CRT by Broutin and Wang, where they prove that it is possible to reconstruct the original tree in distribution. We describe an enrichment of the cut-tree transformation, which endows the cut tree with information we call a consistent collection of routings. We show this procedure is well-defined under minimal conditions on the R-trees. We then show that, for the case of the Brownian CRT and the $α$-stable trees with $α\in (1, 2)$, the original tree and the Poisson process of cuts thereon can both be almost surely reconstructed from the enriched cut-trees. For the latter results, our methods make essential use of the self-similarity and re-rooting invariance of these trees.

preprint2015arXiv

The Brownian continuum random tree as the unique solution to a fixed point equation

In this note, we provide a new characterization of Aldous' Brownian continuum random tree as the unique fixed point of a certain natural operation on continuum trees (which gives rise to a recursive distributional equation). We also show that this fixed point is attractive.

preprint2014arXiv

A line-breaking construction of the stable trees

We give a new, simple construction of the $α$-stable tree for $α\in (1,2]$. We obtain it as the closure of an increasing sequence of $\mathbb{R}$-trees inductively built by gluing together line-segments one by one. The lengths of these line-segments are related to the the increments of an increasing $\mathbb{R}_+$-valued Markov chain. For $α= 2$, we recover Aldous' line-breaking construction of the Brownian continuum random tree based on an inhomogeneous Poisson process.

preprint2013arXiv

The scaling limit of the minimum spanning tree of the complete graph

Consider the minimum spanning tree (MST) of the complete graph with n vertices, when edges are assigned independent random weights. Endow this tree with the graph distance renormalized by n^{1/3} and with the uniform measure on its vertices. We show that the resulting space converges in distribution, as n tends to infinity, to a random measured metric space in the Gromov-Hausdorff-Prokhorov topology. We additionally show that the limit is a random binary R-tree and has Minkowski dimension 3 almost surely. In particular, its law is mutually singular with that of the Brownian continuum random tree or any rescaled version thereof. Our approach relies on a coupling between the MST problem and the Erdös-Rényi random graph. We exploit the explicit description of the scaling limit of the Erdös-Rényi random graph in the so-called critical window, established by the first three authors in an earlier paper, and provide a similar description of the scaling limit for a "critical minimum spanning forest" contained within the MST.

preprint2011arXiv

Quantum Heisenberg models and their probabilistic representations

These notes give a mathematical introduction to two seemingly unrelated topics: (i) quantum spin systems and their cycle and loop representations, due to Tóth and Aizenman-Nachtergaele; (ii) coagulation-fragmentation stochastic processes. These topics are nonetheless related, as we argue that the lengths of cycles and loops satisfy an effective coagulation-fragmentation process. This suggests that their joint distribution is Poisson-Dirichlet. These ideas are far from being proved, but they are backed by several rigorous results, notably of Dyson-Lieb-Simon and Schramm.