Postgraduate research opportunities

Graph representations

Graph representations became crucial with the advent of the computer era for storing graphs in computer memory. However, graph representations, e.g. those involving patterns in words, are also useful in solving problems on graphs as they may allow transferring a graph problem to that on other objects hence solving it.

Number of places

1

Opens

31 March 2020

Duration

3 - 4 years

Eligibility

BSc or MSc in mathematics or computer science is required.

Project Details

Graph representations became crucial with the advent of the computer era for storing graphs in computer memory, so the question of finding efficient representations of graphs is definitely timely. However, graph representations are also interesting and useful in solving (hard) problems on graphs. Indeed, certain representations may allow one to transfer a graph problem to a problem on objects representing the graphs, then solving the problem on those objects and returning a solution on the graphs. For example, in 1918, Heinz Prüfer discovered a fascinating relationship between labelled trees with n vertices and sequences of length n-2 made of the elements of the set {1,2,…,n}. This relationship is a bijection and it allowed Prüfer to prove Cayley’s formula for the number of n-vertex labelled trees. In this project, we will focus on various ways to represent graphs on n vertices using words (i.e. strings of symbols) over an alphabet {1,2,…,n}. In particular, in the studies, we will deploy certain graph orientations helping us with representation questions, and also use patterns in words.  

How to apply

Please email to Dr Sergey Kitaev if you would like to apply for this opportunity.