BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Rotor walk is a deterministic analogue of simple random walk. For any given graph, we construct a rotor configuration for which the escape rate of the corresponding rotor walk is equal to the escape rate of simple random walk, and thus answer a question of Florescu, Ganguly, Levine, and Peres (2014).
We study rotor walks on transient graphs with initial rotor configuration sampled from the oriented wired uniform spanning forest (OWUSF) measure. We show that the expected number of visits to any vertex by the rotor walk is at most equal to the expected number of visits by the simple random walk. In particular, this implies that this walk is transient. When these two numbers coincide, we show that the rotor configuration at the end of the process also has the law of OWUSF. Furthermore, if the graph is vertex-transitive, we show that the average number of visits by n consecutive rotor walks converges to the Green function of the simple random walk as n tends to infinity. This answers a question posed by Florescu, Ganguly, Levine, and Peres (2014).
The k-tiling problem for a convex polytope P is the problem of covering Rd with translates of P using a discrete multiset Λ of translation vectors, such that every point in Rd is covered exactly k times, except possibly for the boundary of P and its translates. A classical result in the study of tiling problems is a theorem of McMullen that a convex polytope P that 1-tiles Rd with a discrete multiset Λ can, in fact, 1-tile Rd with a lattice L. A generalization of McMullen's theorem for k-tiling was conjectured by Gravin, Robins, and Shiryaev, which states that if P k-tiles Rd with a discrete multiset Λ, then P m-tiles Rd with a lattice L for some m. In this paper, we consider the case when P k-tiles Rd with a discrete multiset Λ such that every element of Λ is contained in a quasi-periodic set Q (i.e. a finite union of translated lattices). This is motivated by the result of Gravin, Kolountzakis, Robins, and Shiryaev, showing that for d∈{2,3}, if a polytope P k-tiles Rd with a discrete multiset Λ, then P m-tiles Rd with a quasi-periodic set Q for some m. Here we show for all values of d that if a polytope P k-tiles Rd with a discrete multiset Λ that is contained in a quasi-periodic set Q that satisfies a mild hypothesis, then P m-tiles Rd with a lattice L for some m. This strengthens the results of Gravin, Kolountzakis, Robins, and Shiryaev, and is a step in the direction of proving the conjecture of Gravin et al.
A maximal minor M of the Laplacian of an n-vertex Eulerian digraph Γ gives rise to a finite group Zn−1/Zn−1M known as the sandpile (or critical) group S(Γ) of Γ. We determine S(Γ) of the generalized de Bruijn graphs Γ=DB(n,d) with vertices 0,…,n−1 and arcs (i,di+k) for 0≤i≤n−1 and 0≤k≤d−1, and closely related generalized Kautz graphs, extending and completing earlier results for the classical de Bruijn and Kautz graphs. Moreover, for a prime p and an n-cycle permutation matrix X∈GLn(p) we show that S(DB(n,p)) is isomorphic to the quotient by ⟨X⟩ of the centralizer of X in PGLn(p). This offers an explanation for the coincidence of numerical data in sequences A027362 and A003473 of the OEIS, and allows one to speculate upon a possibility to construct normal bases in the finite field Fpn from spanning trees in DB(n,p).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.