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ⁿ 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ⁿ 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ⁿ is known to be (pⁿ+p^n-1)/3. In Chapter 4, we show that if a sum-free subset of \mathbb{F}_pⁿ is larger than pⁿ/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.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2024

Author dc:creator

• Versteegen, Leo

Advisor dc:contributor.advisor

• Wolf, Julia

• Abelian Groups
• Common
• Cops and robber
• Domination Game
• Fp
• Game
• Graph
• Graph code
• Sum-free set

Licence

• https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/39f67e83-8fb7-4ab0-b0e7-b8be2c7163f9/download
• https://creativecommons.org/licenses/by/4.0/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.109626

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/370042