Algorithmic and Computational Graph Theory and Game Theory

点击翻译按钮获取中文摘要

Fundamental problems in computer science revolve around the discovery of efficient algorithms. Designing fast algorithms or proving that no fast algorithm exists intimately relies, in many cases, on geometrical and graph theoretic characteristics of the problem. Graph Theory has long been recognized as one of the most fruitful fields for the formal study of such problems. Recently, with the massive amounts of network data that are becoming computationally available (including some social and biological networks), mathematicians and computer scientists have studied topological characteristics that such networks exhibit. One aspect of my research will focus on the analysis of large-scale networks. This work includes a precise topological analysis and proposing generative mechanisms. Such mechanisms have potential to help us reason, at a general level, about the ways in which real-world networks are organized. These models have novel algorithmic and graph-theoretic questions that I plan to study. A closely related line of research is the study of statistical aspects of graphs and the probabilistic treatment of random graphs - graphs that are generated by some random process. Random graphs also allow researchers to consider graphs that are both large and unstructured. Random lifts, a new versatile class of random graphs, is defined by, roughly speaking, randomly selecting the permutation that defines the lift. This allows us to design somewhat structured random graphs to model a variety of important naturally-occurring random graphs. Thus, determining the typical properties of a lift, such as their chromatic number, and how they reflect the properties of the base graph are very important and is another aspect of my research. I also intend to work on some of the classically more important problems in graph colouring, a traditionally important area of graph theory for computer scientists. In some of these problems, I will make use of the discharging method - the tool by which the famous Four Colour Problem was finally proved in 1979.