Repository logo
 

Games, Graphs, and Groups


Type

Thesis

Change log

Authors

Versteegen, Leo 

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 Fpn for primes p≥5 and large n and in Zp for large primes p.

We call a graph H strongly common if for every colouring ϕ 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 ϕ. 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 AFpn is sum-free if it contains no elements x, y, and z such that x+y=z. If p≡2mod3, the maximal size of a sum-free in Fpn is known to be (pn+pn−1)/3. In Chapter 4, we show that if a sum-free subset of Fpn 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⋅5n−1.

We say that a family C of graphs on n vertices is a linear graph code if the symmetric difference of the edge sets of any two graphs in C is also the edge set of a graph in 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 εH>0 such that the size of a linear graph code without a copy of H is at most 2(n2)/nε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 ⌈10n/17⌉ 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.

Description

Date

2024-04-16

Advisors

Wolf, Julia

Keywords

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

Qualification

Doctor of Philosophy (PhD)

Awarding Institution

University of Cambridge
Sponsorship
Trinity College External Researcher Studentship