Grant: Discovery Grants Program - Individual

This program of research studies computational and theoretical problems in graphs and networks. Graphs and networks each consist of a collection of nodes, some pairs of which are connected by edges. As one example, consider the network that we can construct from the World Wide Web: let each webpage be represented by its own node and then join node A to node B if webpage A has a link to webpage B. This example, known as the Web Graph, contains the structural information of the web, but none of its content. One key question that we now want to ask is whether it is possible to find collections of webpages that share related content, when all we have to work with is the network structure of the Web Graph. Another research goal involves studying decompositions of graphs. As an example of a problem that can be modelled as a graph decomposition, suppose that N delegations, each with an equal number of delegates, are in attendance at a convention. During the convention there is a banquet at which there are only round tables, each able to seat T people. A seating arrangement of the delegates so that each pair of delegations has two delegates seated side by side, and also so that no pair of people from the same delegation sit at the same table is the same as a type of graph decomposition known as a T-cycle system of order N. One kind of question that we want to study is: how many different seating arrangements are there for particular values of T and N? Supposing that the delegations have been grouped into alliances such that each delegation belongs to at most one alliance, we can also ask: how many different alliances do there have to be so that there is a seating arrangement where no table has all T of its people from the same alliance (in addition to the previous requirements for the seating arrangement)? This type of question can be solved by studying colourings of graph decompositions. In addition to theoretical advances involving graphs and networks, this research program has applications that range from seating arrangements and scheduling, to intelligence gathering based on analysing networks, to studying genetic and ecological connectivity in marine species, and to aspects of human population genetics.