To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Topics in discrete random… - University of Gothenburg, Sweden Till startsida
Sitemap

# Topics in discrete random structures

Doctoral thesis
Authors Anders Martinsson 2017-04-28 Alexander Holroyd, Microsoft Research, USA 978-91-7597-561-0 Chalmers University of Technology Gothenburg 2017 Department of Mathematical Sciences en publications.lib.chalmers.se/record... First--passage percolation, Cartesian power graph, third moment argument, jigsaw puzzle, shotgun assembly, monotone paths, non-Markovian coupling, high dimension, coupling inequality Probability Theory and Statistics, Discrete Mathematics

## Abstract

This thesis presents four papers on problems in discrete probability. A common theme of the articles is to take some class of discrete structures, impose some randomness, and then consider what happens asymptotically as the size of the structure tends to infinity. Paper I concerns first--passage percolation on Cartesian graph powers $G^d$ of some fixed base graph $G$ as $d\rightarrow\infty$. We propose a natural asymptotic lower bound on the first--passage time between $(v, v, \dots)$ and $(w, w, \dots)$, which we call the critical time. Our main result characterizes when this lower bound is sharp. As a consequence we are able to determine the so--called diagonal time constant of $\mathbb{Z}^d$ as $d\rightarrow\infty$ for a large class of passage time distributions. In Paper II we investigate a phenomenon of non--standard couplings of Markov chains, where two copies of a chain can be coupled to meet almost surely while their total variation distance stays bounded away from $0$. We show that the supremum total variation distance that can be maintained in this context is $\frac{1}{2}$. Paper III resolves affirmatively a recent conjecture by Lavrov and Loh that a uniformly chosen random edge--ordering of $K_n$ contains a monotone Hamiltonian path with probability tending to $1$ as $n\rightarrow\infty$. We further prove a partial result regarding the limiting behavior of the number of such paths, suggesting that this number, when appropriately rescaled, has log--normal distribution in the large $n$ limit. The topic of Paper IV is a model for a random $n\times n$ jigsaw puzzle, recently proposed by Mossel and Ross, where the shape of each edge of a piece is chosen uniformly out of $q$ possibilities. The main question is whether this puzzle has a unique solution. We say that two solutions are similar if they only differ by permutations of duplicate pieces and rotations of pieces with rotational symmetries. We show that, with probability tending to $1$ as $n\rightarrow \infty$, this puzzle has multiple non--similar solutions when $2\leq q \leq \frac{2}{\sqrt{e}} n$, all solutions are similar when $q\geq (2+\varepsilon)n$ for any $\varepsilon>0$, and the solution is unique when $q=\omega(n)$.

Page Manager: Webmaster|Last update: 9/11/2012
Share:

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?