9 citations · 42 across the 19 of their papers we have counts for
21 papers
Capturing an Invisible Robber using Separators
Igor Potapov, Tymofii Prokopenko, John Sylvester
We study the zero-visibility cops and robbers game, where the robber is invisible to the cops until they are caught. This differs from the classic game where full information about…
Time-Biased Random Walks and Robustness of Expanders
Sam Olesker-Taylor, Thomas Sauerwald, John Sylvester
Random walks on expanders play a crucial role in Markov Chain Monte Carlo algorithms, derandomization, graph theory, and distributed computing. A desirable property is that they ar…
Coupled transport equations with freezing
Krzysztof Burdzy, John Sylvester
We study a system of two coupled transport equations with freezing. The solutions freeze in time when they are equal. We prove existence and uniqueness of continuous solutions if t…
Rumors with Changing Credibility
Charlotte Out, Nicolás Rivera, Thomas Sauerwald +1
Randomized rumor spreading processes diffuse information on an undirected graph and have been widely studied. In this work, we present a generic framework for analyzing a broad cla…
Mean-Biased Processes for Balanced Allocations
Dimitrios Los, Thomas Sauerwald, John Sylvester
We introduce a new class of balanced allocation processes which bias towards underloaded bins (those with load below the mean load) either by skewing the probability by which a bin…
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
Édouard Bonnet, Julien Duron, John Sylvester +2
We show that for any natural number , there is a constant and a subgraph-closed class having, for any natural , at most graphs on vertices up to isomorphism, bu…
Cops and Robbers on Multi-Layer Graphs
Jessica Enright, Kitty Meeks, William Pettersson +1
We generalise the popular cops and robbers game to multi-layer graphs, where each cop and the robber are restricted to a single layer (or set of edges). We show that initial intuit…
Balanced Allocations with Heterogeneous Bins: The Power of Memory
Dimitrios Los, Thomas Sauerwald, John Sylvester
We consider the allocation of balls (jobs) into bins (servers). In the standard Two-Choice process, at each step we first sample two bins uniformly at rand…
Cover and Hitting Times of Hyperbolic Random Graphs
Marcos Kiwi, Markus Schepers, John Sylvester
We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range . In…
The Power of Filling in Balanced Allocations
Dimitrios Los, Thomas Sauerwald, John Sylvester
We introduce a new class of balanced allocation processes which are primarily characterized by ``filling'' underloaded bins. A prototypical example is the Packing process: At each…
Bounds on the Twin-Width of Product Graphs
William Pettersson, John Sylvester
Twin-width is a graph width parameter recently introduced by Bonnet, Kim, Thomassé & Watrigant. Given two graphs and and a graph product , we address the question: i…
A New Temporal Interpretation of Cluster Editing
Cristiano Bocci, Chiara Capresi, Kitty Meeks +1
The NP-complete graph problem Cluster Editing seeks to transform a static graph into a disjoint union of cliques by making the fewest possible edits to the edges. We introduce a na…
Balanced Allocations: Caching and Packing, Twinning and Thinning
Dimitrios Los, Thomas Sauerwald, John Sylvester
We consider the sequential allocation of balls (jobs) into bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintai…
Tangled Paths: A Random Graph Model from Mallows Permutations
Jessica Enright, Kitty Meeks, William Pettersson +1
We introduce the random graph which results from taking the union of two paths of length , where the vertices of one of the paths have been relabelled a…
The Cover Time of a (Multiple) Markov Chain with Rational Transition Probabilities is Rational
John Sylvester
The cover time of a Markov chain on a finite state space is the expected time until all states are visited. We show that if the cover time of a discrete-time Markov chain with rati…
Multiple Random Walks on Graphs: Mixing Few to Cover Many
Nicolás Rivera, Thomas Sauerwald, John Sylvester
Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running multiple rando…
The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
Jessica Enright, Duncan Lee, Kitty Meeks +2
Understanding spatial correlation is vital in many fields including epidemiology and social science. Lee, Meeks and Pettersson (Stat. Comput. 2021) recently demonstrated that impro…
Time Dependent Biased Random Walks
John Haslegrave, Thomas Sauerwald, John Sylvester
We study the biased random walk where at each step of a random walk a "controller" can, with a certain small probability, move the walk to an arbitrary neighbour. This model was in…
The Power of Two Choices for Random Walks
Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald +1
We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two in…
The dispersion time of random walks on finite graphs
Nicolas Rivera, Alexandre Stauffer, Thomas Sauerwald +1
We study two random processes on an -vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. In both processes particles start from an arbitrary bu…
Random walk hitting times and effective resistance in sparsely connected Erdős-Rényi random graphs
John Sylvester
We prove expectation and concentration results for the following random variables on an Erdős-Rényi random graph in the sparsely connected regime $\lo…