Alexander Roberts

activity

20162022

most citedExact stability for Turán's Theorem

6 citations · 6 across the 5 of their papers we have counts for

collaborators

11 papers

math.CO2022

Shotgun assembly of random graphs

Tom Johnston, Gal Kronenberg, Alexander Roberts +1

In the graph shotgun assembly problem, we are given the balls of radius $r$ around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the E…

math.CO2022

Decomposing random permutations into order-isomorphic subpermutations

Carla Groenland, Tom Johnston, Dániel Korándi +3

Two permutations $s$ and $t$ are $k$ -similar if they can be decomposed into subpermutations $s^{1}, \dots, s^{k}$ and $t^{1}, \dots, t^{k}$ such that $s^{i}$ is order-isomorphic to $t^{i}$ f…

math.CO2020

Isoperimetric stability in lattices

Ben Barber, Joshua Erde, Peter Keevash +1

We obtain isoperimetric stability theorems for general Cayley digraphs on $Z^{d}$ . For any fixed $B$ that generates $Z^{d}$ over $Z$ , we characterise the app…

math.CO2020★ 6 cited

Exact stability for Turán's Theorem

Dániel Korándi, Alexander Roberts, Alex Scott

Turán's Theorem says that an extremal $K_{r + 1}$ -free graph is $r$ -partite. The Stability Theorem of Erdős and Simonovits shows that if a $K_{r + 1}$ -free graph with $n$ vertices has…

math.CO2019

Shotgun reconstruction in the hypercube

Michał Przykucki, Alexander Roberts, Alex Scott

Mossel and Ross raised the question of when a random colouring of a graph can be reconstructed from local information, namely the colourings (with multiplicity) of balls of given r…

math.PR2019

Parking on the integers

Michał Przykucki, Alexander Roberts, Alex Scott

Models of parking in which cars are placed randomly and then move according to a deterministic rule have been studied since the work of Konheim and Weiss in the 1960s. Recently, Da…

math.CO2019

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Natasha Morrison, Alexander Roberts, Alex Scott

Fix $k \geq 2$ and let $H$ be a graph with $χ (H) = k + 1$ containing a critical edge. We show that for sufficiently large $n$ , the unique $n$ -vertex $H$ -free graph containing the maxi…

math.CO2018

Vertex-isoperimetric stability in the hypercube

Michał Przykucki, Alexander Roberts

Harper's Theorem states that, in a hypercube, among all sets of a given fixed size the Hamming balls have minimal closed neighbourhoods. In this paper we prove a stability-like res…

math.CO2018

Approximating the position of a hidden agent in a graph

Hannah Guggiari, Alexander Roberts, Alex Scott

A cat and mouse play a pursuit and evasion game on a connected graph $G$ with $n$ vertices. The mouse moves to vertices $m_{1}, m_{2}, \dots$ of $G$ where $m_{i}$ is in the closed neighbou…

math.PR2018

Exceptional graphs for the random walk

Juhan Aru, Carla Groenland, Tom Johnston +3

If $W$ is the simple random walk on the square lattice $Z^{2}$ , then $W$ induces a random walk $W_{G}$ on any spanning subgraph $G\subset \mathbb…

math.CO2016

Stability results for graphs with a critical edge

Alexander Roberts, Alex Scott

The classical stability theorem of Erdős and Simonovits states that, for any fixed graph with chromatic number $k + 1 \geq 3$ , the following holds: every $n$ -vertex graph that is $H$ -…