Tom Johnston

activity

20182025

most citedExact hyperplane covers for subsets of the hypercube

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

collaborators

Showing 2022 · math.COShow all

6 papers · 2 filters

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★ 4 cited

The rainbow saturation number is linear

Natalie Behague, Tom Johnston, Shoham Letzter +2

Given a graph $H$ , we say that an edge-coloured graph $G$ is $H$ -rainbow saturated if it does not contain a rainbow copy of $H$ , but the addition of any non-edge in any colour crea…

math.CO2022

Perfect shuffling with fewer lazy transpositions

Carla Groenland, Tom Johnston, Jamie Radcliffe +1

A lazy transposition $(a, b, p)$ is the random permutation that equals the identity with probability $1 - p$ and the transposition $(a, b) \in S_{n}$ with probability $p$ . How long must a…

math.CO2022

Short reachability networks

Carla Groenland, Tom Johnston, Jamie Radcliffe +1

We investigate the following generalisation of permutation networks. We say a sequence $T = (T_{1}, \dots, T_{ℓ})$ of transpositions in $S_{n}$ forms a $t$ -reachability network if, for ev…

math.CO2022★ 2 cited

Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron

Paul Bastide, Carla Groenland, Hugo Jacob +1

For given positive integers $k$ and $n$ , a family $F$ of subsets of ${1, \dots, n}$ is $k$ -antichain saturated if it does not contain an antichain of size $k$ , but adding…

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…