Games, Graphs, and Groups

This dissertation contains various combinatorial results about games, graphs and finite Abelian groups. A linear configuration is said to be *common* in an Abelian group $G$ if every 2-colouring of $G$ yields at least as many monochromatic instances of the configuration as a randomly chosen colouring. In Chapter 2, we show that every configuration containing a 4-term arithmetic progression is uncommon in $\mathbb{F}_p^n$ for primes $p\geq 5$ and large $n$ and in $\mathbb{Z}_p$ for large primes $p$. We call a graph $H$ *strongly common* if for every colouring $\phi$ of $K_n$ with two colours, the number of monochromatic copies of $H$ is at least the number of monochromatic copies of $H$ in a random colouring of $K_n$ with the same density of colour classes as $\phi$. In Chapter 3, we prove that if a graph has odd girth but is not a cycle, then it is not strongly common. We also discuss the commonness property for hypergraphs. A set $A\subset \mathbb{F}_p^n$ is *sum-free* if it contains no elements $x$, $y$, and $z$ such that $x+y=z$. If $p\equiv 2 \mod 3$, the maximal size of a sum-free in $\mathbb{F}_p^n$ is known to be $(p^n+p^{n-1})/3$. In Chapter 4, we show that if a sum-free subset of $\mathbb{F}_p^n$ is larger than $p^n/3-p^{n-1}/6+p^{n-2}$, then it is contained in $(p+1)/3$ cosets of a subspace of codimension 1. For $p=5$, we prove the stronger bound $1.2\cdot 5^{n-1}$. We say that a family $\mathcal{C}$ of graphs on $n$ vertices is a *linear graph code* if the symmetric difference of the edge sets of any two graphs in $\mathcal{C}$ is also the edge set of a graph in $\mathcal{C}$. In Chapter 5, we investigate the maximal size of a linear graph code that does not contain a copy of a fixed graph $H$. In particular, we show that for almost all graphs $H$ with an even number of edges, there exists $\varepsilon_H>0$ such that the size of a linear graph code without a copy of $H$ is at most $2^{\binom{n}{2}}/n^{\varepsilon_H}$. The game *cops and robbers* is played on a graph $G$ by two players, where one of them controls $k$ cop pieces and the other controls a single robber piece. The players take turns to move their pieces along the edges between vertices of $G$, and the cop player attempts to have his pieces *catch* the robber piece. In Chapter 6, we present a new algorithm that determines for any $G$ and $k$ whether the cops can catch the robbers with optimal play. We will also prove sufficient conditions for a cop-win in terms of the independence and domination numbers of $G$. In the *domination game*, two players called Dominator and Staller select vertices in a graph $G$ alternately. A vertex is said to be *dominated* if it has been selected or is adjacent to a selected vertex. Each selected vertex must dominate a new vertex, and the game ends once every vertex in $G$ is dominated. Dominator aims to keep the game as short as possible, while Staller tries to achieve the opposite. In Chapter 7, we prove that for any graph $G$ on $n$ vertices, Dominator has a strategy to end the game in at most $3n/5$ moves. In Chapter 8, we show that if $G$ has $n$ vertices and minimum degree 2, then Dominator has a strategy to end the game in at most $\lceil 10n/17 \rceil$ moves. Finally, in Chapter 9, we show that if we replace the notion of domination by *total domination*, then Dominator has a strategy to end the game in $3n/4$ moves. / Trinity College External Researcher Studentship