Listed on this page are current research projects being offered for the Vacation Scholarship Program.
For more information on this research group see: Discrete Mathematics The list of project is under construction.
Structure and Colourings of Squares of Oriented Graphs
Graph colouring can be described using graph homomorphisms: a k-colouring of a graph is a homomorphism from that graph to the complete graph on k vertices . The same idea can be used to define colourings of oriented graphs, in which each edge is assigned a direction. Although ordinary graph colouring provides useful intuition, oriented colouring introduces additional constraints. In particular, two vertices in an oriented colouring must receive different colours whenever they are joined by an arc or by a directed path of length two. Thus, every oriented colouring induces a proper colouring of an associated undirected graph in which two vertices are adjacent whenever one can be reached from the other by a directed path of length at most two. In this project we study the structure of these oriented graph “squares”, with an eye towards understanding which oriented graphs produce squares for which the chromatic number may be computed efficiently.
Some familiarity with introductory graph theory, as well as some programming experience will be helpful in this project. The precise research question(s) to be considered will be chosen based on the scholar's interests and background knowledge.
Contact: Chris Duffy christopher.duffy@unimelb.edu.au
Multi-Colour Ramsey Numbers with Switching
Ramsey theory studies the unavoidable structures that arise when constructing large random graphs (i.e., assigning the edges of a complete graph to be either red or blue). In this project we study a variant of the classical Ramsey parameter where we extend the number of colours and permit a switching operation, which permutes the colours incident with a vertex. The switching operations define a group action on the set of edge-coloured graphs on a fixed number of vertices, partitioning this set into orbits. This gives rise to a Ramsey-style parameter that captures the spirit of the classical parameter but for which one may apply standard tools and constrictions from the study of switching in edge-coloured graphs.
Contact: Chris Duffy christopher.duffy@unimelb.edu.au
Here is the 2025-2026 list of research Projects.
Lattice models of polymer systems
Long chain polymers like DNA can be modelled by walks, polygons, trees, and various other combinatorial structures embedded in lattices. This project aims to investigate new polymer models. This can be approached using exact solution techniques or computational methods like series enumeration and random sampling.
Contact: Nick Beaton nrbeaton@unimelb.edu.au
Counting pattern-avoiding permutations and other combinatorial objects
A pattern-avoiding permutation is a permutation whose entries are restricted to avoid one or more substructure. They have simple descriptions but the problem of counting them can range from trivially easy to devilishly difficult. They are connected to a range of other combinatorial objects like lattice paths, binary trees, and inversion sequences. This project will look at some open problems in pattern-avoiding permutations and related objects. Some experience with Mathematica and/or Python would be helpful.
Contact: Nick Beaton nrbeaton@unimelb.edu.au