PhD Defence: The Localization Game and Generalized Ramsey Numbers

Candidate: Rehan Malik

Supervisor: Dr. Anthony Bonato and Dr. Peter Danziger

Abstract
Complex networks are often studied via pairwise interactions, but multiple-vertex inter-actions give rise to complex hypergraphs. These hypergraphs encompass various scenarios, such as group emails, scholarly collaborations, and protein interactions. The ILT model utilizes transitivity as an evolutionary mechanism, capturing properties observed in social networks such as densification, low average distances, and high clustering coefficients. We propose a new model called the Iterated Local Transitivity Hypergraph (ILTH) model, which utilizes transitivity iteratively to generate hypergraphs. Our findings demonstrate that the ILTH model generates hypergraphs similar to real-world complex hypergraphs, including densification and low average distance. Furthermore, we analyze motifs and their properties within the ILTH model.

Tic-Tac-Toe is a positional game played on a hypergraph by two players, Xeno and Ophelia, where Xeno takes the first turn. We explore Tic-Tac-Toe on designs, initially on STS(n), presenting Xeno’s winning strategies. Using principles from Latin squares and transversal designs, we confirm that Tic-Tac-Toe on an affine plane of order 4 is a Xeno win, previously proven only computationally. Through analysis of Tic-Tac-Toe on transversal designs TD(k, n), we establish bounds on k and examine TD(k, n) with a small number of groups. Our findings reveal a winning strategy for Xeno when k = 2, 3 while emphasizing that score-optimization is not always optimal for Xeno. We analyze Tic-Tac-Toe on TD(4, 4) and determine that Ophelia can force a draw. We analyze the weak version of Tic-Tac-Toe, called the Maker-Breaker variant, on TD(k, n), (v, k, λ)-BIBD, and on hypergraphs. We show that Maker wins if v > 25 and v = 16, while Breaker wins when v = 4, 13. We explore game behavior on subhypergraphs obtained by removing hyperedges or points. Competition networks are formed through adversarial interactions between agents. We conducted an empirical analysis using a centrality measure. We observed that it accurately predicts the importance of agents in various real-world networks, including food webs, conflict networks, and voting data from the game show Survivor.