5 citations · 24 across the 18 of their papers we have counts for
7 papers · 1 filter
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 around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the E…
The rainbow saturation number is linear
Natalie Behague, Tom Johnston, Shoham Letzter +2
Given a graph , we say that an edge-coloured graph is -rainbow saturated if it does not contain a rainbow copy of , but the addition of any non-edge in any colour crea…
Perfect shuffling with fewer lazy transpositions
Carla Groenland, Tom Johnston, Jamie Radcliffe +1
A lazy transposition is the random permutation that equals the identity with probability and the transposition with probability . How long must a…
Short reachability networks
Carla Groenland, Tom Johnston, Jamie Radcliffe +1
We investigate the following generalisation of permutation networks. We say a sequence of transpositions in forms a -reachability network if, for ev…
Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
Paul Bastide, Carla Groenland, Hugo Jacob +1
For given positive integers and , a family of subsets of is -antichain saturated if it does not contain an antichain of size , but adding…
Improved bounds for 1-independent percolation on
Paul Balister, Tom Johnston, Michael Savery +1
A 1-independent bond percolation model on a graph is a probability distribution on the spanning subgraphs of in which, for all vertex-disjoint sets of edges and …