More Like this

1. The hit-and-run version of top-to-random

   https://doi.org/10.1017/jpr.2021.96  

   Boardman, Samuel; Rudolf, Daniel; Saloff-Coste, Laurent (January 2022, Journal of Applied Probability)

   Abstract We study an example of a hit-and-run random walk on the symmetric group $$\mathbf S_n$$ . Our starting point is the well-understood top-to-random shuffle. In the hit-and-run version, at each single step , after picking the point of insertion j uniformly at random in $$\{1,\ldots,n\}$$ , the top card is inserted in the j th position k times in a row, where k is uniform in $$\{0,1,\ldots,j-1\}$$ . The question is, does this accelerate mixing significantly or not? We show that, in $L^2$ and sup-norm, this accelerates mixing at most by a constant factor (independent of n ). Analyzing this problem in total variation is an interesting open question. We show that, in general, hit-and-run random walks on finite groups have non-negative spectrum. 

   more » « less
2. A non-increasing tree growth process for recursive trees and applications

   https://doi.org/10.1017/S0963548320000073  

   Eslava, Laura (January 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract We introduce a non-increasing tree growth process $$((T_n,{\sigma}_n),\, n\ge 1)$$ , where T n is a rooted labelled tree on n vertices and σ n is a permutation of the vertex labels. The construction of ( T n , σ n ) from ( T n −1 , σ n −1 ) involves rewiring a random (possibly empty) subset of edges in T n −1 towards the newly added vertex; as a consequence T n −1 ⊄ T n with positive probability. The key feature of the process is that the shape of T n has the same law as that of a random recursive tree, while the degree distribution of any given vertex is not monotone in the process. We present two applications. First, while couplings between Kingman’s coalescent and random recursive trees were known for any fixed n , this new process provides a non-standard coupling of all finite Kingman’s coalescents. Second, we use the new process and the Chen–Stein method to extend the well-understood properties of degree distribution of random recursive trees to extremal-range cases. Namely, we obtain convergence rates on the number of vertices with degree at least $$c\ln n$$ , c ∈ (1, 2), in trees with n vertices. Further avenues of research are discussed. 

   more » « less
3. Finding the root in random nearest neighbor trees

   Brandenberger, Anna M; Marcussen, Cassandra; Mossel, Elchanan; Sudan, Madhu (November 2024, ACM Corr)

   We study the inference of network archaeology in growing random geometric graphs. We consider the root finding problem for a random nearest neighbor tree in dimension d∈N, generated by sequentially embedding vertices uniformly at random in the d-dimensional torus and connecting each new vertex to the nearest existing vertex. More precisely, given an error parameter ε>0 and the unlabeled tree, we want to efficiently find a small set of candidate vertices, such that the root is included in this set with probability at least 1−ε. We call such a candidate set a confidence set. We define several variations of the root finding problem in geometric settings -- embedded, metric, and graph root finding -- which differ based on the nature of the type of metric information provided in addition to the graph structure (torus embedding, edge lengths, or no additional information, respectively). We show that there exist efficient root finding algorithms for embedded and metric root finding. For embedded root finding, we derive upper and lower bounds (uniformly bounded in n) on the size of the confidence set: the upper bound is subpolynomial in 1/ε and stems from an explicit efficient algorithm, and the information-theoretic lower bound is polylogarithmic in 1/ε. In particular, in d=1, we obtain matching upper and lower bounds for a confidence set of size Θ(log(1/ε)loglog(1/ε)). 

   more » « less
4. Multitrees in Random Graphs

   https://doi.org/10.37236/10804  

   Frieze, Alan; Pegden, Wesley (January 2023, The Electronic Journal of Combinatorics)

   Let $$N=\binom{n}{2}$$ and $$s\geq 2$$. Let $$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$$ be $$s$$ independent permutations of the edges $$E(K_n)$$ of the complete graph $$K_n$$. A MultiTree is a set $$I\subseteq [N]$$ such that the edge sets $$E_{I,j}$$ induce spanning trees for $$j=1,2,\ldots,s$$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $$O(n\log n)$$ bound for $$s\geq 3$$. 

   more » « less
5. Equal sums in random sets and the concentration of divisors

   https://doi.org/10.1007/s00222-022-01177-y  

   Ford, Kevin; Green, Ben; Koukoulopoulos, Dimitris (June 2023, Inventiones mathematicae)

   Abstract We study the extent to which divisors of a typical integer n are concentrated. In particular, defining $$\Delta (n) := \max _t \# \{d | n, \log d \in [t,t+1]\}$$ Δ ( n ) : = max t # { d | n , log d ∈ [ t , t + 1 ] } , we show that $$\Delta (n) \geqslant (\log \log n)^{0.35332277\ldots }$$ Δ ( n ) ⩾ ( log log n ) 0.35332277 … for almost all n , a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for the concentration of divisors of a random permutation and of a random polynomial over a finite field. Most of the paper is devoted to a study of the following much more combinatorial problem of independent interest. Pick a random set $${\textbf{A}} \subset {\mathbb {N}}$$ A ⊂ N by selecting i to lie in $${\textbf{A}}$$ A with probability 1/ i . What is the supremum of all exponents $$\beta _k$$ β k such that, almost surely as $$D \rightarrow \infty $$ D → ∞ , some integer is the sum of elements of $${\textbf{A}} \cap [D^{\beta _k}, D]$$ A ∩ [ D β k , D ] in k different ways? We characterise $$\beta _k$$ β k as the solution to a certain optimisation problem over measures on the discrete cube $$\{0,1\}^k$$ { 0 , 1 } k , and obtain lower bounds for $$\beta _k$$ β k which we believe to be asymptotically sharp. 

   more » « less