Geometric Graph Theory
We studied the following problem. Suppose you are given a finite number of points, say n of them, in the plane such that no three points lie on a line. Then, suppose you draw line segments between every pair of chosen points (which is possible since no three are on a line). Lastly, suppose you colour every line segment so that lines which cross or which share an endpoint are coloured differently; such a colouring is depicted in the accompanying picture. What is the largest number of colours required to colour the line segments of your n point set? Rephrasing the problem, what is the “worst” way in which you can lay down n points so that the most number of colours are needed to colour the edges in this way? As the number of points gets larger, this becomes very difficult to answer precisely.
I was introduced to graph theory in the last semester of my Science degree; being keen on geometry as well, I was curious to discover the links between these two fields and which open problems were important. Geometric graph theory falls within a broader mathematical discipline called combinatorics, which in our context can be briefly described in its broadest sense as the study of configurations and combinations of mathematical objects. In a more general setting, combinatorics can be seen as the mathematical backbone of computer science and algorithmics, so there is much practical interest in studying the problems this field has to offer.
Having completed this project, my passion for graph theory and combinatorics has grown; as I commence my honours year, I hope to improve my writing abilities and time management skills so that I can develop these fields as much as I can in the time I have left. Experiencing a collaborative effort with my supervisor, Michael Payne, was invaluable; in the future, I wish to work primarily as a collaborative mathematician, as I believe the only way you can have significant impact as a modern day mathematician is if you build up your network and work with as many others as you can. In the future, I want to improve my critical thinking skills and my ability to “think on my feet” more effectively, which I hope will come with more experiences like this one.
Tim Banova was one of the recipients of a 2017/18 AMSI Vacation Research Scholarship.