Conference Agenda

The $L^1$-compression exponent of a graph quantifies the extent to which the graph fails to bi-Lipschitz embed into $L^1$-spaces. These spaces provide a natural target geometry and the compression exponent is known to capture useful geometric information, for instance about the speed of random walks. In this talk, we will describe a probabilistic characterization of this exponent in terms of connectivity decay of bond percolation models with large marginals.

In the special case of Cayley graphs of groups, the result makes progress on a program suggested by Russell Lyons. Notably, the general result does not require any symmetry assumption. The proof uses a generalization of a construction of bond percolations developed by the authors previously for the symmetric setting, which uses Poisson point processes on so-called spaces with measured walls and yields explicit bounds on the connectivity function.

This talk is based on joint work with Chiranjib Mukherjee.

A sequence of random variables is called exchangeable if the its law is invariant under finite permutations. This is a weaker assumption than independence and often quite plausible in applications. It approximately corresponds to the intuition that the random variables are observed in no particular order. One thus expects edge exchangeable models to be appropriate when we observe \emph{interactions} rather than \emph{agents} in no particular order. We study certain graph-theoretic properties of graphs produced by edge exchangeable processes.

We restrict ourselves to the setting of undirected simple (multi-)graphs with a countable latent vertex set. Let $\mathbb{N}_2$ be the set of unordered pairs of distinct natural numbers. For a set $A$ denote by $\mathcal{P}(A)$ the set of probability measures on $A$. A De-Finietti type result for edge exchangeable models is known and in our setting says that all such models can be obtained by a suitable choice of $\mathcal{M}$ in the following sampling procedure. Let $G_0=\{\emptyset,\emptyset\}$ be the empty undirected multigraph. Let $\mathcal{M} \in \mathcal{P}(\mathcal{P}(\mathbb{N}_2))$. Sample, $\mathcal{W} \sim \mathcal{M}$. Then recursively set $$G_{n+1} := G_n \cup e_{n+1}, e_{n+1} \sim \mathcal{W}.$$

Less tersely, start with an empty graph and given $\mathcal{W} \in P(\mathcal{M})$ (which may have been random), repeatedly sample edges iid from $\mathcal{W}$ and add them, as well as any necessary vertices, to the graph. It is also natural, and technically useful, to consider the poissonized version in which for each $e \in \mathbb{N}_2$ we run an independent of everything else poisson process with intensity $\mathcal{W}(\{e\})$ which counts the number of copies of edge $e$. We will be interested in properties (number of vertices, connectedness, completeness) which are invariant under identifying parallel edges, which we will henceforth do. We abuse notation and use $G_n$ also for this process. In the poissonized case we see that this reduces to studying a model in which each edge arrives with an independent exponential time with parameter $\mathcal{W}(\{e\})$. Our results also apply to and are in fact proven for this exponential time version and recovered for the initial setting by de-poissonization.

Notice that graphs produced in this way have vertex sets with random size and random contents and that isolated vertices never occur. This is quite different from classical random graph settings. Moreover, we study the full trajectory of the graph-valued stochastic process rather than a sequence of independent graphs.

We define an apparently new notion for graph-valued stochastic processes. Namely, that of eventual forever connectedness, which as the name implies, is the event that there exists some (random) time after which the graph is always connected. We make three main contributions, which we do not state explicitly as to avoid introducing more notation and definitions. Conditioning on $\mathcal{W}$ we,

\begin{itemize} \item give a necessary and sufficient condition on $\mathcal{W}$ for $G_n$ to be eventually forever connected and therein illustrate that it is not a very restrictive assumption. \item show that if $G_n$ is eventually forever connected and the variance of the number of vertices goes to infinity then the number of vertices is asymptotically Gaussian. This proves a conjecture of Janson in the connected regime. \item give a necessary and sufficient condition on $\mathcal{W}$ for $G_n$ to be eventually forever essentially the complete graph. Janson had previously found a sufficient condition. \end{itemize}

A new component is created precisely when an edge brings two new vertices. For the first result the main difficulty is that these events are dependent. We proceed by bounding the amount of dependence and use a pseudo-converse of the first Borel-Cantelli lemma. For the second, the main difficulty is that whether a vertex is present is not independent of the other vertices. We notice that the phenomenon which is an obstacle to connectedness (edges which bring two new vertices) witnesses this dependence. Therefore it turns out that making the topological assumption of eventual forever connectedness helps prove our distributional result. We consider this surprising observation the highlight of the associated forthcoming paper. The proof proceeds by constructing a coupling to an urn scheme which displays the necessary independence. For the final result we proceed by proving a general result regarding the ordering of collections of exponential random variables and then realize the theorem as a corollary.

Consider a homogenous Poisson Point Process on $\mathbb{R}^d$, equipped with convex grains, i.e. i.i.d. copies of a random convex body that is rotationally-invariant in distribution. We define for such a convex body a non-increasing sequence of diameters. The first diameter is the classical diameter of the convex body. The $i$-th diameter is then defined as the diameter of the orthogonal projection of the body from the previous step along the $(i-1)$-st diameter onto the $(d-i+1)$-dimensional hyperplane. This projected body is then projected further when determining the next diameter. We state several criteria on the diameter distribution and moment conditions for the volume of the convex body that result in either a dense process, i.e. the whole space is covered by the grains, or robustness, i.e. the union of the grains has an unbounded connected component for any intensity of the underlying Poisson process. Importantly, we do not impose any conditions on the joint distribution of the diameters. If the grains are chosen to be euclidean balls, it is known that density and robustness are equivalent. We show in our general model that in any dimension $d\geq 2$ there exists grain distributions where robustness does not imply density.

Let $T$ be a supercritical Galton-Watson tree with mean offspring number $m>1$ and finite variance. Let $\alpha >0$ and assume that every node in the tree on level $n$ is "marked" with a probability of $e^{-n\alpha}$, independently of all other nodes. Let $\partial T$ be the set of infinite self-avoiding paths in the tree, starting at the root. There is a standard metric on $\partial T$: The distance of two elements in $\partial T$ is $e^{-n}$ if $n$ is the level of the last node they have in common. We show that for GW-almost every tree, the subset of paths which are marked infinitely often does almost surely have Hausdorff dimension $\log(m)-\alpha$, if $m>e^{\alpha}$. For $m<e^{\alpha}$, the set is empty almost surely. In the critical case $m=e^\alpha$ the set is nonempty with dimension $0$.