BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Omer Angel

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

ResearcherUnclaimed source record
math.PRmath.COmath-phmath.MPcond-mat.stat-mechDiscrete MathematicsDistributed, Parallel, and Cluster Computingmath.CAmath.GRmath.MGSocial and Information Networks

Catalog footprint

What is connected

33works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

33 published item(s)

preprint2026arXiv

Voter Model stability with respect to conservative noises

The notions of noise sensitivity and stability were recently extended for the voter model. In this model, the vertices of a graph have opinions that are updated by uniformly selecting edges. We further extend stability results to different classes of perturbations. We consider two different types of noise: in the first one, an exclusion process is performed on the edge selections, while in the second, independent Brownian motions are applied to such a sequence. In both cases, we prove stability of the consensus opinion provided the noise is run for a short amount of time, depending on the underlying graph structure. This is done by analyzing the expected size of the pivotal set, whose definition differs from the usual one in order to reflect the change associated with these noises.

0 citations0 reviewsNo code linkedOpen access
preprint2025arXiv

The largest common subtree of two random trees

We study the size and structure of the largest common subtree (LCS) between two independent Bienaymé trees conditioned to have size $n$. When the trees are critical with finite $2$nd and $(2+κ)$th moment respectively for some $κ>0$, we prove that the LCS has size of order $\sqrt{n}$, and is approximated by the length of three paths meeting at a central node. Moreover, we show that the largest common subtree between two critical independent Bienaymé trees with size $n$ and finite second moments may be much larger than $\sqrt{n}$, implying that our result is tight. We also pose a number of open questions and suggestions for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The number of spanning clusters of the uniform spanning tree in three dimensions

Let ${\mathcal U}_δ$ be the uniform spanning tree on $δ\mathbb{Z}^{3}$. A spanning cluster of ${\mathcal U}_δ$ is a connected component of the restriction of ${\mathcal U}_δ$ to the unit cube $[0,1]^{3}$ that connects the left face $\{ 0 \} \times [0,1]^{2}$ to the right face $\{ 1 \} \times [0,1]^{2}$. In this note, we will prove that the number of the spanning clusters is tight as $δ\to 0$, which resolves an open question raised by Benjamini (1999).

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

The string of diamonds is nearly tight for rumour spreading

For a rumour spreading protocol, the spread time is defined as the first time that everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with its asynchronous variant, and show that for any $n$-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by $O \left({n}^{1/3}{\log^{2/3} n}\right)$. This improves the $O(\sqrt n)$ upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of $O(\log n)$, as illustrated by the string of diamonds graph. We also show that if for a pair $α,β$ of real numbers, there exists infinitely many graphs for which the two spread times are $n^α$ and $n^β$ in expectation, then $0\leqα\leq 1$ and $α\leq β\leq \frac13 + \frac23 α$; and we show each such pair $α,β$ is achievable.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Boundaries of planar graphs, via circle packings

We provide a geometric representation of the Poisson and Martin boundaries of a transient, bounded degree triangulation of the plane in terms of its circle packing in the unit disc. (This packing is unique up to Möbius transformations.) More precisely, we show that any bounded harmonic function on the graph is the harmonic extension of some measurable function on the boundary of the disk, and that the space of extremal positive harmonic functions, that is, the Martin boundary, is homeomorphic to the unit circle. All our results hold more generally for any "good"-embedding of planar graphs, that is, an embedding in the unit disc with straight lines such that angles are bounded away from $0$ and $π$ uniformly, and lengths of adjacent edges are comparable. Furthermore, we show that in a good embedding of a planar graph the probability that a random walk exits a disc through a sufficiently wide arc is at least a constant, and that Brownian motion on such graphs takes time of order $r^2$ to exit a disc of radius $r$. These answer a question recently posed by Chelkak (2014).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Increasing subsequences of random walks

Given a sequence of $n$ real numbers $\{S_i\}_{i\leq n}$, we consider the longest weakly increasing subsequence, namely $i_1<i_2<\dots <i_L$ with $S_{i_k} \leq S_{i_{k+1}}$ and $L$ maximal. When the elements $S_i$ are i.i.d. uniform random variables, Vershik and Kerov, and Logan and Shepp proved that $\mathbb{E} L=(2+o(1)) \sqrt{n}$. We consider the case when $\{S_i\}_{i\leq n}$ is a random walk on $\mathbb{R}$ with increments of mean zero and finite (positive) variance. In this case, it is well known (e.g., using record times) that the length of the longest increasing subsequence satisfies $\mathbb{E} L\geq c\sqrt{n}$. Our main result is an upper bound $\mathbb{E} L\leq n^{1/2 + o(1)}$, establishing the leading asymptotic behavior. If $\{S_i\}_{i\leq n}$ is a simple random walk on $\mathbb{Z}$, we improve the lower bound by showing that $\mathbb{E} L \geq c\sqrt{n} \log{n}$. We also show that if $\{\mathbf{S}_i\}$ is a simple random walk in $\mathbb{Z}^2$, then there is a subsequence of $\{\mathbf{S}_i\}_{i\leq n}$ of expected length at least $cn^{1/3}$ that is increasing in each coordinate. The above one-dimensional result yields an upper bound of $n^{1/2 + o(1)}$. The problem of determining the correct exponent remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Multicolour Poisson Matching

Consider several independent Poisson point processes on R^d, each with a different colour and perhaps a different intensity, and suppose we are given a set of allowed family types, each of which is a multiset of colours such as red-blue or red-red-green. We study translation-invariant schemes for partitioning the points into families of allowed types. This generalizes the 1-colour and 2-colour matching schemes studied previously (where the sets of allowed family types are the singletons {red-red} and {red-blue} respectively). We characterize when such a scheme exists, as well as the optimal tail behaviour of a typical family diameter. The latter has two different regimes that are analogous to the 1-colour and 2-colour cases, and correspond to the intensity vector lying in the interior and boundary of the existence region respectively. We also address the effect of requiring the partition to be a deterministic function (i.e. a factor) of the points. Here we find the optimal tail behaviour in dimension 1. There is a further separation into two regimes, governed by algebraic properties of the allowed family types.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Restrictions of Hölder continuous functions

For $0<α<1$ let $V(α)$ denote the supremum of the numbers $v$ such that every $α$-Hölder continuous function is of bounded variation on a set of Hausdorff dimension $v$. Kahane and Katznelson (2009) proved the estimate $1/2 \leq V(α)\leq 1/(2-α)$ and asked whether the upper bound is sharp. We show that in fact $V(α)=\max\{1/2,α\}$. Let $\dim_{H}$ and $\overline{\dim}_{M}$ denote the Hausdorff and upper Minkowski dimension, respectively. The upper bound on $V(α)$ is a consequence of the following theorem. Let $\{B(t): t\in [0,1]\}$ be a fractional Brownian motion of Hurst index $α$. Then, almost surely, there exists no set $A\subset [0,1]$ such that $\overline{\dim}_{M} A>\max\{1-α,α\}$ and $B\colon A\to \mathbb{R}$ is of bounded variation. Furthermore, almost surely, there exists no set $A\subset [0,1]$ such that $\overline{\dim}_{M} A>1-α$ and $B\colon A\to \mathbb{R}$ is $β$-Hölder continuous for some $β>α$. The zero set and the set of record times of $B$ witness that the above theorems give the optimal dimensions. We also prove similar restriction theorems for deterministic self-affine functions and generic $α$-Hölder continuous functions. Finally, let $\{\mathbf{B}(t): t\in [0,1]\}$ be a two-dimensional Brownian motion. We prove that, almost surely, there is a compact set $D\subset [0,1]$ such that $\dim_{H} D\geq 1/3$ and $\mathbf{B}\colon D\to \mathbb{R}^2$ is non-decreasing in each coordinate. It remains open whether $1/3$ is best possible.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Unimodular Hyperbolic Triangulations: Circle Packing and Random Walk

We show that the circle packing type of a unimodular random plane triangulation is parabolic if and only if the expected degree of the root is six, if and only if the triangulation is amenable in the sense of Aldous and Lyons. As a part of this, we obtain an alternative proof of the Benjamini-Schramm Recurrence Theorem. Secondly, in the hyperbolic case, we prove that the random walk almost surely converges to a point in the unit circle, that the law of this limiting point has full support and no atoms, and that the unit circle is a realisation of the Poisson boundary. Finally, we show that the simple random walk has positive speed in the hyperbolic metric.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Classification of Half Planar Maps

We characterize all translation invariant half planar maps satisfying a certain natural domain Markov property. For p-angulations with p \ge 3 where all faces are simple, we show that these form a one-parameter family of measures H^{(p)}_{alpha}. For triangulations we also establish existence of a phase transition which affects many properties of these maps. The critical maps are the well known half plane uniform infinite planar maps. The sub-critical maps are identified as all possible limits of uniform measures on finite maps with given boundary and area.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Tight Upper Bound on Acquaintance Time of Graphs

In this note we confirm a conjecture raised by Benjamini et al. \cite{BST} on the acquaintance time of graphs, proving that for all graphs $G$ with $n$ vertices it holds that $\AC(G) = O(n^{3/2})$, which is tight up to a multiplicative constant. This is done by proving that for all graphs $G$ with $n$ vertices and maximal degree $Δ$ it holds that $\AC(G) \leq 20 Δn$. Combining this with the bound $\AC(G) \leq O(n^2/Δ)$ from \cite{BST} gives the foregoing uniform upper bound of all $n$-vertex graphs. We also prove that for the $n$-vertex path $P_n$ it holds that $\AC(P_n)=n-2$. In addition we show that the barbell graph $B_n$ consisting of two cliques of sizes $\ceil{n/2}$ and $\floor{n/2}$ connected by a single edge also has $\AC(B_n) = n-2$. This shows that it is possible to add $Ω(n^2)$ edges to $P_n$ without changing the $\AC$ value of the graph.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Percolations on random maps I: half-plane models

We study Bernoulli percolations on random lattices of the half-plane obtained as local limit of uniform planar triangulations or quadrangulations. Using the characteristic spatial Markov property or peeling process of these random lattices we prove a surprisingly simple universal formula for the critical threshold for bond and face percolations on these graphs. Our techniques also permit us to compute off-critical and critical exponents related to percolation clusters such as the volume and the perimeter.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Scaling limit of the invasion percolation cluster on a regular tree

We prove existence of the scaling limit of the invasion percolation cluster (IPC) on a regular tree. The limit is a random real tree with a single end. The contour and height functions of the limit are described as certain diffusive stochastic processes. This convergence allows us to recover and make precise certain asymptotic results for the IPC. In particular, we relate the limit of the rescaled level sets of the IPC to the local time of the scaled height function.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A pattern theorem for random sorting networks

A sorting network is a shortest path from 12..n to n..21 in the Cayley graph of the symmetric group S(n) generated by nearest-neighbor swaps. A pattern is a sequence of swaps that forms an initial segment of some sorting network. We prove that in a uniformly random n-element sorting network, any fixed pattern occurs in at least cn^2 disjoint space-time locations, with probability tending to 1 exponentially fast as n tends to infinity. Here c is a positive constant which depends on the choice of pattern. As a consequence, the probability that the uniformly random sorting network is geometrically realizable tends to 0.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Deterministic approximations of random reflectors

Within classical optics, one may add microscopic "roughness" to a macroscopically flat mirror so that parallel rays of a given angle are reflected at different outgoing angles. Taking the limit (as the roughness becomes increasingly microscopic) one obtains a flat surface that reflects randomly, i.e., the transition from incoming to outgoing ray is described by a probability kernel (whose form depends on the nature of the microscopic roughness). We consider two-dimensional optics (a.k.a. billiards) and show that every random reflector on a line that satisfies a necessary measure-preservation condition (well established in the theory of billiards) can be approximated by deterministic reflectors in this way.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Localization for Linearly Edge Reinforced Random Walks

We prove that the linearly edge reinforced random walk (LRRW) on any graph with bounded degrees is recurrent for sufficiently small initial weights. In contrast, we show that for non-amenable graphs the LRRW is transient for sufficiently large initial weights, thereby establishing a phase transition for the LRRW on non-amenable graphs. While we rely on the description of the LRRW as a mixture of Markov chains, the proof does not use the magic formula. We also derive analogous results for the vertex reinforced jump process.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Phase Transition for Dyadic Tilings

A dyadic tile of order n is any rectangle obtained from the unit square by n successive bisections by horizontal or vertical cuts. Let each dyadic tile of order n be available with probability p, independently of the others. We prove that for p sufficiently close to 1, there exists a set of pairwise disjoint available tiles whose union is the unit square, with probability tending to 1 as n->infinity, as conjectured by Joel Spencer in 1999. In particular we prove that if p=7/8, such a tiling exists with probability at least 1-(3/4)^n. The proof involves a surprisingly delicate counting argument for sets of unavailable tiles that prevent tiling.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The TASEP speed process

In the multi-type totally asymmetric simple exclusion process (TASEP) on the line, each site of Z is occupied by a particle labeled with some number, and two neighboring particles are interchanged at rate one if their labels are in increasing order. Consider the process with the initial configuration where each particle is labeled by its position. It is known that in this case a.s. each particle has an asymptotic speed which is distributed uniformly on [-1,1]. We study the joint distribution of these speeds: the TASEP speed process. We prove that the TASEP speed process is stationary with respect to the multi-type TASEP dynamics. Consequently, every ergodic stationary measure is given as a projection of the speed process measure. This generalizes previous descriptions restricted to finitely many classes. By combining this result with known stationary measures for TASEPs with finitely many types, we compute several marginals of the speed process, including the joint density of two and three consecutive speeds. One striking property of the distribution is that two speeds are equal with positive probability and for any given particle there are infinitely many others with the same speed. We also study the partially asymmetric simple exclusion process (ASEP). We prove that the states of the ASEP with the above initial configuration, seen as permutations of Z, are symmetric in distribution. This allows us to extend some of our results, including the stationarity and description of all ergodic stationary measures, also to the ASEP.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to zeta(3)=1/1^3+1/2^3+1/3^3+... as n goes to infinity. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k > log_2 log n+omega(1), where omega(1) is any function going to infinity with n, then the minimum bounded-depth spanning tree still has weight tending to zeta(3) as n -> infinity, and that if k < log_2 log n, then the weight is doubly-exponentially large in log_2 log n - k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k < log_2 log n - omega(1), a simple greedy algorithm is asymptotically optimal, and when k > log_2 log n+omega(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m = const * n, if k > log_2 log n+omega(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 <= k <= log_2 log n-omega(1), the weight tends to (1-2^{-k}) sqrt{8m/n} [sqrt{2mn}/2^k]^{1/(2^k-1)} in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of 2^{1/(2^k-1)}.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Discrete low-discrepancy sequences

Holroyd and Propp used Hall's marriage theorem to show that, given a probability distribution pi on a finite set S, there exists an infinite sequence s_1,s_2,... in S such that for all integers k >= 1 and all s in S, the number of i in [1,k] with s_i = s differs from k pi(s) by at most 1. We prove a generalization of this result using a simple explicit algorithm. A special case of this algorithm yields an extension of Holroyd and Propp's result to the case of discrete probability distributions on infinite sets.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Global divergence of spatial coalescents

We study several fundamental properties of a class of stochastic processes called spatial Lambda-coalescents. In these models, a number of particles perform independent random walks on some underlying graph G. In addition, particles on the same vertex merge randomly according to a given coalescing mechanism. A remarkable property of mean-field coalescent processes is that they may come down from infinity, meaning that, starting with an infinite number of particles, only a finite number remains after any positive amount of time, almost surely. We show here however that, in the spatial setting, on any infinite and bounded-degree graph, the total number of particles will always remain infinite at all times, almost surely. Moreover, if G=Z^d, and the coalescing mechanism is Kingman's coalescent, then starting with N particles at the origin, the total number of particles remaining is of order (log* N)^d at any fixed positive time (where log* is the inverse tower function). At sufficiently large times the total number of particles is of order (log* N)^{d-2}, when d>2. We provide parallel results in the recurrent case d=2. The spatial Beta-coalescents behave similarly, where log log N is replacing log* N.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Rotor walks on general trees

The rotor walk on a graph is a deterministic analogue of random walk. Each vertex is equipped with a rotor, which routes the walker to the neighbouring vertices in a fixed cyclic order on successive visits. We consider rotor walk on an infinite rooted tree, restarted from the root after each escape to infinity. We prove that the limiting proportion of escapes to infinity equals the escape probability for random walk, provided only finitely many rotors send the walker initially towards the root. For i.i.d. random initial rotor directions on a regular tree, the limiting proportion of escapes is either zero or the random walk escape probability, and undergoes a discontinuous phase transition between the two as the distribution is varied. In the critical case there are no escapes, but the walker's maximum distance from the root grows doubly exponentially with the number of visits to the root. We also prove that there exist trees of bounded degree for which the proportion of escapes eventually exceeds the escape probability by arbitrarily large o(1) functions. No larger discrepancy is possible, while for regular trees the discrepancy is at most logarithmic.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Random Sorting Networks

A sorting network is a shortest path from 12...n to n...21 in the Cayley graph of S_n generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as n->infinity the space-time process of swaps converges to the product of semicircle law and Lebesgue measure. We conjecture that the trajectories of individual particles converge to random sine curves, while the permutation matrix at half-time converges to the projected surface measure of the 2-sphere. We prove that, in the limit, the trajectories are Holder-1/2 continuous, while the support of the permutation matrix lies within a certain octagon. A key tool is a connection with random Young tableaux.

0 citations0 reviewsNo code linkedOpen access