PhD Defence: The Localization Game and Generalized Ramsey Numbers

Candidate: Brittany Pittman

Supervisors: Dr. Anthony Bonato and Dr. Michelle Delcourt

Abstract
We focus on the localization game on graphs as well as generalized Ramsey numbers. The localization game is a pursuit-evasion game in which a set of cops attempt to locate an invisible robber using distance probes. We define two novel variations of the localization game. First, we introduce the localization capture time parameter, which is the number of rounds needed to locate the robber when both players are playing optimally. We present bounds on the localization capture time for trees and interval graphs. We conjecture that, in general, the capture time of a graph is linear in the order of the graph, and we present families of graphs for which this conjecture holds. We also extend the localization game to directed graphs and present bounds on the localization number of directed graphs, including bounds in terms of width parameters and bounds using strong components and linear programming.

Given a graph and a subgraph, the generalized Ramsey numbers refer to the number of colors needed to color the edges of the graph such that any copy of the subgraph contains at least q colors for some q. We prove two instances of the generalized Ramsey numbers in the bipartite case. We provide a new proof for a known value of the generalized Ramsey numbers. For another instance of the generalized Ramsey numbers, we present an improved upper bound.