Hi, I'm Matthew Askes, MSc

About Me


Bio

I was born in Tauranga, but currently reside in Wellington, NZ. I moved to Wellington to study a BSc at Victoria University of Wellington (VUW), and never left. I have a passion for mathematics and computer science, and have recently finished my MSc in mathematics. My primary areas of research involve algorithmic graph theory, graph games, and online algorithms.

Education

2022

Master of Science with Distinction

Victoria University of Wellington, Wellington, NZ

Subject: Mathematics

2021

Bachelor of Science with First Class Honours

Victoria University of Wellington, Wellington, NZ

Major: Mathematics

2019

Bachelor of Science

Victoria University of Wellington, Wellington, NZ

Majors: Computer Science and Mathematics

Projects


Title page generated by vuwthesis class

VUW Thesis

A LaTex class

A LaTex class for styling an MSc or PhD thesis at VUW

This is an outgrowth of my MSc thesis. I found that the available template was lacking, so I made my own.

Graph Blitz logo and title

Graph Blitz

A mobile game

Graph Blitz is a small mobile game for Android based on the graph colouring game and online graph colouring.

Graph Blitz is about mathematical graphs and the strategies used to colour them. The goal of the game is to colour graphs such that no too vertices have the same colour. It may sound easy, but the computer is playing against you.

The primary strategy used by the AI is the Activation Strategy, a description of which is available in my honours thesis.

Graph Blitz logo and title

Graph Blitz Website

A website

The Graph Blitz website is a basic page for the app along with some statistics. The stats are tracked in the game, and then the website checks the database to display them. Both the frontend and backend run on the Google Cloud Platform. For more info how the site works click the button below.

Research


Online, Computable and Punctual Structure Theory

Matthew Askes, Rod Downey

Logic Journal of the IGPL, August 2022, jzac065
DOI: 10.1093/jigpal/jzac065

Abstract: Several papers (e.g. [7, 23, 42]) have recently sought to give general frameworks for online structures and algorithms ([4]), and seeking to connect, if only by analogy, online and computable structure theory. These initiatives build on earlier work on online colouring and other combinatorial algorithms by Bean [10], Kierstead, Trotter et al. [48, 54, 57] and others, as we discuss below. In this paper we will look at such frameworks and illustrate them with examples from the first author’s MSc Thesis ([58]). In this thesis, Askes looks at online, adversarial online and strongly online algorithms and structures. Additionally, we prove some new theorems about online algorithms on graphs of bounded pathwidth as well as some new results on punctually 1-decidable structures.

Download pdf

Adversarial and Online Algorithms

Masters Thesis

DOI: 10.26686/wgtn.20279553

Abstract: In this thesis we explore a variety of online and adversarial algorithms. We primarily explore the following online and adversarial algorithms; the perfect code game, adversarial online colouring, the chain decomposition game, and strongly online graphs.

The perfect code game is a new adversarial game played on graphs in which players take turns constructing perfect codes. We provide definitions for perfect codes and the perfect code game, along with some motivation from coding theory. We will prove upper bounds for both cycle and path graphs. We also prove an upper bound for graphs of bounded pathwidth. Finally, we explore the perfect code game in graphs of bounded degree.

We will create a new game called the adversarial online colouring game, this game takes elements from both online and adversarial algorithms. We will begin with some discussion and a definition of adversarial online colouring. We will then prove several results related to graph degree. We conclude with a proof that the adversarial online colouring game on trees is determined only by the number of colours and the number of vertices (assuming that both players have a chance at winning).

The chain decomposition game is another adversarial game, but this time played on partial orders. We introduce the chain decomposition game and demonstrate two results relating to upper and lower bounds for the game. We also prove a result on the online adversarial version of the game.

We introduce strongly online graphs and graph colouring as a new algorithmic parameterization to online graph colouring. A strongly online graph is an online graph where at each stage 𝑠 we can see a ball of increasing radius about each vertex. We will prove several bounds (upper and lower) on the online chromatic number of strongly online graphs. For example, we show that every strongly online graph can be coloured in twice its chromatic number. We prove that every strongly online graph with even pathwidth 𝑘 can be online coloured with 2𝑘 + 1 colours. Then, after introducing a natural notion of strongly online pathwidth, we prove that there is a strongly online graph with no finite strongly online path decomposition.

Download pdf

Graph Algorithms with Hostile Partners

Honours Thesis

Abstract: A graph algorithm with a hostile partner is a game played between two players, Alice and Bob. In each game Alice and Bob take it in turns to construct some object. Alice wins if the object has a specific property, and Bob wins if it doesn't. In this report we will explore a variety of games along with variations that allow Alice and Bob to play more than once per turn. We will also examine various strategies for both Alice and Bob. And, for each strategy we will see under what conditions Alice or Bob will always win. The four main games we will consider are; the dominating game, the independent dominating game, the colouring game, and the marking game.
Download PDF

Other Work


Braids and the Braid Group

An introduction

Abstract: The study of braids and the braid group is a vast topic. This report introduces the basic ideas of braids and the braid group. This report is aimed at anyone with little to no knowledge of braids but who has some understanding of knot theory.
Download PDF