Search

There are numerous randomized algorithms to generate spanning trees in a given ambient graph; several target the uniform distribution on trees (UST), while in practice the fastest and most frequently used draw random weights on the edges and then employ a greedy algorithm to choose the minimum-weight spanning tree (MST). Though MST is a workhorse in applications, the mathematical properties of random MST are far less explored than those of UST. In this paper we develop tools for the quantitative study of random MST. We consider the standard case that the weights are drawn i.i.d. from a single distribution on the real numbers, as well as successive generalizations that lead to \emph{product measures}, where the weights are independently drawn from arbitrary distributions.

Marstrand's theorem states that applying a generic rotation to a planar set $A$ before projecting it orthogonally to the $x$-axis almost surely gives an image with the maximal possible dimension $\min(1, \dim A)$. We first prove, using the transversality theory of Peres-Schlag locally, that the same result holds when applying a generic complex linear-fractional transformation in $PSL(2,\C)$ or a generic real linear-fractional transformation in $PGL(3,\R)$. We next show that, under some necessary technical assumptions, transversality locally holds for restricted families of projections corresponding to one-dimensional subgroups of $PSL(2,\C)$ or $PGL(3,\R)$. Third, we demonstrate, in any dimension, local transversality and resulting projection statements for the families of closest-point projections to totally-geodesic subspaces of hyperbolic and spherical geometries., Comment: To appear in Math. Proc. Cambridge Philos. Soc

Every Thurston map $f\colon S^2\rightarrow S^2$ on a $2$-sphere $S^2$ induces a pull-back operation on Jordan curves $\alpha\subset S^2\setminus P_f$, where $P_f$ is the postcritical set of $f$. Here the isotopy class $[f^{-1}(\alpha)]$ (relative to $P_f$) only depends on the isotopy class $[\alpha]$. We study this operation for Thurston maps with four postcritical points. In this case a Thurston obstruction for the map $f$ can be seen as a fixed point of the pull-back operation. We show that if a Thurston map $f$ with a hyperbolic orbifold and four postcritical points has a Thurston obstruction, then one can "blow up" suitable arcs in the underlying $2$-sphere and construct a new Thurston map $\widehat f$ for which this obstruction is eliminated. We prove that no other obstruction arises and so $\widehat f$ is realized by a rational map. In particular, this allows for the combinatorial construction of a large class of rational Thurston maps with four postcritical points. We also study the dynamics of the pull-back operation under iteration. We exhibit a subclass of our rational Thurston maps with four postcritical points for which we can give positive answer to the global curve attractor problem., Comment: 72 pages, 22 figues

We establish an uncountable amenable ergodic Roth theorem, in which the acting group is not assumed to be countable and the space need not be separable. This generalizes a previous result of Bergelson, McCutcheon and Zhang, and complements a result of Zorin-Kranich. We establish the following two additional results: First, a combinatorial application about triangular patterns in certain subsets of the Cartesian square of arbitrary amenable groups, extending a result of Bergelson, McCutcheon and Zhang for countable amenable groups. Second, a new uniformity aspect in the double recurrence theorem for $\Gamma$-systems for arbitrary uniformly amenable groups $\Gamma$. Our uncountable Roth theorem is crucial in the proof of both of these results., Comment: 35 pages, final version, accepted for publication in DCDS-A

We establish Marstrand-type as well as Besicovich-Federer-type projection theorems for closest-point projections onto hyperplanes in the normed space $\mathbb{R}^{n}$. In particular, we prove that if a norm on $\mathbb{R}^{n}$ is $C^{1,1}$-regular, then the analogues of the well-known statements from the Euclidean setting hold. On the other hand, we construct an example of a $C^{1}$-regular norm in $\mathbb{R}^2$ for which Marstrand-type theorems fail., Comment: 19 pages, 6 figures

We establish Marstrand-type projection theorems for orthogonal projections along geodesics onto m-dimensional subspaces of hyperbolic $n$-space by a geometric argument. Moreover, we obtain a Besicovitch-Federer type characterization of purely unrectifiable sets in terms of these hyperbolic orthogonal projections., Comment: 6 pages, 2 figures

We consider Marstrand type projection theorems for closest-point projections in the normed space $\mathbb{R}^2$. We prove that if a norm on $\mathbb{R}^2$ is regular enough, then the analogues of the well-known statements from the Euclidean setting hold, while they fail for norms whose unit balls have corners. We establish our results by verifying Peres and Schlag's transversality property and thereby also obtain a Besicovitch-Federer type characterization of purely unrectifiable sets., Comment: 20 pages, 6 figures. To appear in Journal of Fractal Geometry

We consider a class of iterated function systems (IFSs) of contracting similarities of $R^n$, introduced by Hutchinson, for which the invariant set possesses a natural H\"older continuous parameterization by the unit interval. When such an invariant set is homeomorphic to an interval, we give necessary conditions in terms of the similarities alone for it to possess a quasisymmetric (and as a corollary, bi-H\"older) parameterization. We also give a related necessary condition for the invariant set of such an IFS to be homeomorphic to an interval., Comment: 22 pages, 5 figures. The 2nd version corresponds to the published version. (Small comments were added and small mistakes and typos corrected.)

We apply the theory of Peres and Schlag to obtain estimates for generic Hausdorff dimension distortion under orthogonal projections on simply connected two dimensional Riemannian manifolds of constant curvature. As a conclusion we obtain appropriate versions of Marstrand theorem, Kaufman's theorem and Falconer's theorem in the above geometrical settings., Comment: 11 pages. Version 2: corrected typos, added references, changed title, improved structure in Section 3. This corresponds to the published version