11 citations · 16 across the 13 of their papers we have counts for
14 papers
Equilibria in a Hypercube Spatial Voting Model
A. Nicholas Day, J. Robert Johnson
We give conditions for equilibria in the following Voronoi game on the discrete hypercube. Two players position themselves in and each receives payoff equal to the meas…
Asymmetry of 2-step Transit Probabilities in 2-Coloured Regular Graphs
Ron Gray, J. Robert Johnson
Suppose that the vertices of a regular graph are coloured red and blue with an equal number of each (we call this a balanced colouring). Since the graph is undirected, the number o…
Partial shuffles by lazy swaps
Barnabás Janzer, J. Robert Johnson, Imre Leader
What is the smallest number of random transpositions (meaning that we swap given pairs of elements with given probabilities) that we can make on an -point set to ensure that eac…
Optimal Resistor Networks
J. Robert Johnson, Mark Walters
Given a graph on n vertices with m edges, each of unit resistance, how small can the average resistance between pairs of vertices be? There are two very plausible extremal construc…
Shattering -sets with Permutations
J. Robert Johnson, Belinda Wickes
Many concepts from extremal set theory have analogues for families of permutations. This paper is concerned with the notion of shattering for permutations. A family o…
Synchronizing Times for -sets in Automata
Natalie C. Behague, J. Robert Johnson
An automaton is synchronizing if there is a word that maps all states onto the same state. Černý's conjecture on the length of the shortest such word is probably the most famous op…
The -free process in the hypercube
J. Robert Johnson, Trevor Pinto
The generation of a random triangle-saturated graph via the triangle-free process has been studied extensively. In this short note our aim is to introduce an analogous process in t…
Transitive Avoidance Games
J. Robert Johnson, Imre Leader, Mark Walters
Positional games are a well-studied class of combinatorial game. In their usual form, two players take turns to play moves in a set (`the board'), and certain subsets are designate…
Multicolour Ramsey Numbers of Odd Cycles
A. Nicholas Day, J. Robert Johnson
We show that for any positive integer there exists an integer and a -colouring of the edges of with no monochromatic odd cycle of length less than . Thi…
Saturated Subgraphs of the Hypercube
J. Robert Johnson, Trevor Pinto
We say is \emph{-saturated} if it is a maximal -free subgraph of the -dimensional hypercube . A graph, , is said to be -semi-saturated if…
Matchings and Hamilton Cycles with Constraints on Sets of Edges
J. Robert Johnson
The aim of this paper is to extend and generalise some work of Katona on the existence of perfect matchings or Hamilton cycles in graphs subject to certain constraints. The most ge…
Set Systems Containing Many Maximal Chains
J. Robert Johnson, Imre Leader, Paul A. Russell
The purpose of this short problem paper is to raise an extremal question on set systems which seems to be natural and appealing. Our question is: which set systems of a given size…
Turán and Ramsey Properties of Subcube Intersection Graphs
J. Robert Johnson, Klas Markström
The discrete cube is a fundamental combinatorial structure. A subcube of is a subset of of its points formed by fixing coordinates and allowing th…
The minimal density of triangles in tripartite graphs
Rahil Baber, J. Robert Johnson, John Talbot
We determine the minimal density of triangles in a tripartite graph with prescribed edge densities. This extends a previous result of Bondy, Shen, Thomassé and Thomassen characteri…