To the top

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

Tell a friend about this page
Print version

Topics in discrete random… - University of Gothenburg, Sweden Till startsida
To content Read more about how we use cookies on

Topics in discrete random structures

Doctoral thesis
Authors Anders Martinsson
Date of public defense 2017-04-28
Opponent at public defense Alexander Holroyd, Microsoft Research, USA
ISBN 978-91-7597-561-0
Publisher Chalmers University of Technology
Place of publication Gothenburg
Publication year 2017
Published at Department of Mathematical Sciences
Language en
Keywords First--passage percolation, Cartesian power graph, third moment argument, jigsaw puzzle, shotgun assembly, monotone paths, non-Markovian coupling, high dimension, coupling inequality
Subject categories Probability Theory and Statistics, Discrete Mathematics


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

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?