Description

Graphs and networks model relationships and can be found all around us. Take for instance web-links on the internet, friends on facebook, roads along the countryside, and so on. The theory of graphs is therefore important to understand the structure of networks and to address network-related problems.

One cool application is the exam scheduling problem. Imagine students at an university have to take their final exams which are to be scheduled by the examiners. If two modules are taken by the same student, for instance AMV and Probability, then their exams must be scheduled at different times to avoid conflict. Of course, everyone wants to get the exams over with as soon as possible. So what is the minimum number of time slots needed to schedule exams without conflict?

If turns out this problem can be re-cast in the language of graph theory and then solved using graph algorithms. In this project you will explore these kind of questions, choose some aspets of graph theory to learn in depth, perhaps look at graph algorithms and even do some simulations of your own.

Examples of topics you can explore are:

• Structural graph theory: connectedness, cuts, matchings, etc.
• Graph colouring and the chromatic number
• Extremal graph theory
• Infinite graphs
• Graph algorithms
• Random graphs

Prerequisites

Algebra II and Analysis in Many Variables II are essential. Probability II is helpful but not required.

Resources

You will be guided to lecture notes or textbooks for your topic. The following may be helpful resources.

• N. Alon and J. Spencer, The Probabilistic Method.
• R. Diestel, Graph Theory.
• D. West, Introduction to Graph Theory.
• J.H. Van Lint and R.M. Wilson, A course in combinatorics.

I will travel occasionally during Michaelmas, so our meetings may be online. Get in touch by email if you have questions.