Abstract
The graph colouring problem is a problem of simple description: for an arbitrary collection of dots with lines connecting pairs of them, how can we colour the dots such that no two dots connected by a line have the same colour, and what is the minimum number of colours possible? This is a very hard problem to solve exactly in general, but we find that by using tools from convex geometry for this very un-geometric problem, we can find the best possible efficiently attainable approximations, and oftentimes exact solutions.
When I tell people “I’m working on the graph colouring problem”, the image conjured in their minds is often, understandably, one of me sitting at my desk thinking very hard about what colours to use for a plot representing some data, which is ironic considering I am colour blind and would doubtlessly be terrible at this. The graph colouring problem (GCP) I have been working on is at once more simple than this —you’ve probably solved an instance of it before — and yet it’s tied for first place for the hardest problem you can give to a computer where a solutions validity can easily be checked, so I’ve had my work cut out for me.
GCP is the problem of assigning colours to the vertices of a given graph such that no two adjacent vertices have the same colour using the least colours possible. This problem is ubiquitous; it comes up in timetabling, where vertices are the events to be scheduled and events connected by an edge cannot occur simultaneously, in quantum mechanics, where vertices are observations of a quantum system and edges represent observables that cannot be made together, and sudoku, where vertices are cells which are adjacent if they are in the same column/row/box. It models any problem where a collection of objects are partitioned while respecting given pairwise incompatibilities between the objects.
A sudoku puzzle; a type of graph colouring problem
We generally consider graphs as not having any specific geometry, and it is this lack of structure which makes the GCP so difficult, as there are classes of graphs with a common structure that people have found ways to colour efficiently, but not for graphs in general. An increasingly popular approach for this type of problem which we took is to approximate a solution using “semidefinite programming”, which minimizes a function over the “positive semidefinite cone”, which is a special convex (like 3D/2D convexity; filled in with no parts jutting inward) cone in a space which matrices that have the property of being “positive semidefinite” live in.
The positive semidefinite cone for 2×2 matrices
A set being convex makes optimisation over it a lot nicer, and the specific conical structure makes solving it “easy” (by a certain definition of easy). My research has led me to reformulate the GCP in geometric terms; colouring n vertices with k colours respecting adjacencies is transformed into finding a projection (like casting a shadow) from n dimensional space to k dimensional space, satisfying certain linear constraints. This is one of many cases where thinking about problems in terms of geometry proves fruitful, as the approximation we get matches the best that exist, and the formulation for exact solutions is very elegant and has great potential for further improvement and faster run times.
Edward Mirco
Curtin University
