{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/370042"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/370042","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Games, Graphs, and Groups","abstract":"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.","abstract_html":"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}pn 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 Kn 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 Kn 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}pn 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}pn is known to be (pn+pn-1)/3. In Chapter 4, we show that if a sum-free subset of \\mathbb{F}pn is larger than pn/3-pn-1/6+pn-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 5n-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 \\varepsilonH>0 such that the size of a linear graph code without a copy of $H$ is at most 2\\binom{n}{2}/n\\varepsilonH. 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.","abstract_has_math":true,"creators":["Versteegen, Leo"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Wolf, Julia"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-04-16","date_published":"2024-04-16","updated_at":"2026-07-22T22:24:27Z","subjects":["Abelian Groups","Common","Cops and robber","Domination Game","Fp","Game","Graph","Graph code","Sum-free set"],"languages":["eng"],"rights":[],"rights_urls":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/39f67e83-8fb7-4ab0-b0e7-b8be2c7163f9/download","https://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.109626","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Wolf, Julia"]},{"key":"dc:contributor.sponsor","label":"Sponsor","values":["Trinity College External Researcher Studentship"]},{"key":"dc:creator","label":"Author","values":["Versteegen, Leo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2024-04-16"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/370042"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Abelian Groups","Common","Cops and robber","Domination Game","Fp","Game","Graph","Graph code","Sum-free set"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/39f67e83-8fb7-4ab0-b0e7-b8be2c7163f9/download","https://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.17863/CAM.109626"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/00692ee0-e6c9-41c5-9410-79354acbce71/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["63988b9fa478f7a009c893b5ac3d6091","87eda9de84448d1f82354d60eee3eb5f"]},{"key":"dc:title","label":"Title","values":["Games, Graphs, and Groups"]}]}],"canonical_facts":{"dc:contributor.advisor":["Wolf, Julia"],"dc:contributor.sponsor":["Trinity College External Researcher Studentship"],"dc:creator":["Versteegen, Leo"],"dc:date.issued":["2024-04-16"],"dc:description.abstract":["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."],"dc:format.checksum.md5":["63988b9fa478f7a009c893b5ac3d6091","87eda9de84448d1f82354d60eee3eb5f"],"dc:identifier.doi":["https://doi.org/10.17863/CAM.109626"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/00692ee0-e6c9-41c5-9410-79354acbce71/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/370042"],"dc:rights":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/39f67e83-8fb7-4ab0-b0e7-b8be2c7163f9/download","https://creativecommons.org/licenses/by/4.0/"],"dc:subject":["Abelian Groups","Common","Cops and robber","Domination Game","Fp","Game","Graph","Graph code","Sum-free set"],"dc:title":["Games, Graphs, and Groups"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:27Z"}