skip to main content


Title: COVER TIME FOR THE FROG MODEL ON TREES
The frog model is a branching random walk on a graph in which particles branch only at unvisited sites. Consider an initial particle density of $\unicode[STIX]{x1D707}$ on the full $d$ -ary tree of height $n$ . If $\unicode[STIX]{x1D707}=\unicode[STIX]{x1D6FA}(d^{2})$ , all of the vertices are visited in time $\unicode[STIX]{x1D6E9}(n\log n)$ with high probability. Conversely, if $\unicode[STIX]{x1D707}=O(d)$ the cover time is $\exp (\unicode[STIX]{x1D6E9}(\sqrt{n}))$ with high probability.  more » « less
Award ID(s):
1811952
NSF-PAR ID:
10159665
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Forum of Mathematics, Sigma
Volume:
7
ISSN:
2050-5094
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Holmsen, Kynčl and Valculescu recently conjectured that if a finite set $X$ with $\ell n$ points in $\mathbb{R}^{d}$ that is colored by $m$ different colors can be partitioned into $n$ subsets of $\ell$ points each, such that each subset contains points of at least $d$ different colors, then there exists such a partition of $X$ with the additional property that the convex hulls of the $n$ subsets are pairwise disjoint. We prove a continuous analogue of this conjecture, generalized so that each subset contains points of at least $c$ different colors, where we also allow $c$ to be greater than $d$ . Furthermore, we give lower bounds on the fraction of the points each of the subsets contains from $c$ different colors. For example, when $n\geqslant 2$ , $d\geqslant 2$ , $c\geqslant d$ with $m\geqslant n(c-d)+d$ are integers, and $\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{m}$ are $m$ positive finite absolutely continuous measures on $\mathbb{R}^{d}$ , we prove that there exists a partition of $\mathbb{R}^{d}$ into $n$ convex pieces which equiparts the measures $\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{d-1}$ , and in addition every piece of the partition has positive measure with respect to at least $c$ of the measures $\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{m}$ . 
    more » « less
  2. null (Ed.)
    Let $f:X\rightarrow X$ be a continuous dynamical system on a compact metric space $X$ and let $\unicode[STIX]{x1D6F7}:X\rightarrow \mathbb{R}^{m}$ be an $m$ -dimensional continuous potential. The (generalized) rotation set $\text{Rot}(\unicode[STIX]{x1D6F7})$ is defined as the set of all $\unicode[STIX]{x1D707}$ -integrals of $\unicode[STIX]{x1D6F7}$ , where $\unicode[STIX]{x1D707}$ runs over all invariant probability measures. Analogous to the classical topological entropy, one can associate the localized entropy $\unicode[STIX]{x210B}(w)$ to each $w\in \text{Rot}(\unicode[STIX]{x1D6F7})$ . In this paper, we study the computability of rotation sets and localized entropy functions by deriving conditions that imply their computability. Then we apply our results to study the case where $f$ is a subshift of finite type. We prove that $\text{Rot}(\unicode[STIX]{x1D6F7})$ is computable and that $\unicode[STIX]{x210B}(w)$ is computable in the interior of the rotation set. Finally, we construct an explicit example that shows that, in general, $\unicode[STIX]{x210B}$ is not continuous on the boundary of the rotation set when considered as a function of $\unicode[STIX]{x1D6F7}$ and $w$ . In particular, $\unicode[STIX]{x210B}$ is, in general, not computable at the boundary of $\text{Rot}(\unicode[STIX]{x1D6F7})$ . 
    more » « less
  3. We examine correlations of the Möbius function over $\mathbb{F}_{q}[t]$ with linear or quadratic phases, that is, averages of the form 1 $$\begin{eqnarray}\frac{1}{q^{n}}\mathop{\sum }_{\deg f0$ if $Q$ is linear and $O(q^{-n^{c}})$ for some absolute constant $c>0$ if $Q$ is quadratic. The latter bound may be reduced to $O(q^{-c^{\prime }n})$ for some $c^{\prime }>0$ when $Q(f)$ is a linear form in the coefficients of $f^{2}$ , that is, a Hankel quadratic form, whereas, for general quadratic forms, it relies on a bilinear version of the additive-combinatorial Bogolyubov theorem. 
    more » « less
  4. Granular flows occur in a wide range of situations of practical interest to industry, in our natural environment and in our everyday lives. This paper focuses on granular flow in the so-called inertial regime, when the rheology is independent of the very large particle stiffness. Such flows have been modelled with the $\unicode[STIX]{x1D707}(I),\unicode[STIX]{x1D6F7}(I)$ -rheology, which postulates that the bulk friction coefficient $\unicode[STIX]{x1D707}$ (i.e. the ratio of the shear stress to the pressure) and the solids volume fraction $\unicode[STIX]{x1D719}$ are functions of the inertial number $I$ only. Although the $\unicode[STIX]{x1D707}(I),\unicode[STIX]{x1D6F7}(I)$ -rheology has been validated in steady state against both experiments and discrete particle simulations in several different geometries, it has recently been shown that this theory is mathematically ill-posed in time-dependent problems. As a direct result, computations using this rheology may blow up exponentially, with a growth rate that tends to infinity as the discretization length tends to zero, as explicitly demonstrated in this paper for the first time. Such catastrophic instability due to ill-posedness is a common issue when developing new mathematical models and implies that either some important physics is missing or the model has not been properly formulated. In this paper an alternative to the $\unicode[STIX]{x1D707}(I),\unicode[STIX]{x1D6F7}(I)$ -rheology that does not suffer from such defects is proposed. In the framework of compressible $I$ -dependent rheology (CIDR), new constitutive laws for the inertial regime are introduced; these match the well-established $\unicode[STIX]{x1D707}(I)$ and $\unicode[STIX]{x1D6F7}(I)$ relations in the steady-state limit and at the same time are well-posed for all deformations and all packing densities. Time-dependent numerical solutions of the resultant equations are performed to demonstrate that the new inertial CIDR model leads to numerical convergence towards physically realistic solutions that are supported by discrete element method simulations. 
    more » « less
  5. null (Ed.)
    Let $(G,\unicode[STIX]{x1D707})$ be a pair of a reductive group $G$ over the $p$ -adic integers and a minuscule cocharacter $\unicode[STIX]{x1D707}$ of $G$ defined over an unramified extension. We introduce and study ‘ $(G,\unicode[STIX]{x1D707})$ -displays’ which generalize Zink’s Witt vector displays. We use these to define certain Rapoport–Zink formal schemes purely group theoretically, i.e. without $p$ -divisible groups. 
    more » « less