Eligibility
BSc or MSc in mathematics or computer science is required.
BSc or MSc in mathematics or computer science is required.
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.
Please email to Dr Sergey Kitaev if you would like to apply for this opportunity.