Algorithmic and Computational Graph Theory and Game Theory

计算机科学的基本问题围绕着高效算法的发现。在许多情况下，设计快速算法或证明不存在快速算法密切依赖于问题的几何和图论特征。长期以来，图论一直被认为是对这类问题进行正式研究的最有成果的领域之一。最近，随着大量的网络数据（包括一些社会和生物网络）在计算上变得可用，数学家和计算机科学家研究了这些网络所表现出的拓扑特征。我研究的一个方面将集中在大规模网络的分析上。这项工作包括精确的拓扑分析和提出生成机制。这种机制有可能帮助我们在一般层面上推理现实世界网络的组织方式。这些模型包含了我打算研究的新颖的算法和图论问题。一个密切相关的研究方向是研究图的统计方面和随机图的概率处理——随机图是由一些随机过程产生的图。随机图还允许研究人员考虑大型且非结构化的图。随机提升是一类新的多用途随机图，它的定义是，粗略地说，随机选择定义提升的排列。这允许我们设计一些结构化的随机图来模拟各种重要的自然发生的随机图。因此，确定一个升降机的典型性质，例如它们的色数，以及它们如何反映基图的性质是非常重要的，也是我研究的另一个方面。我还打算研究图着色中一些经典的更重要的问题，这是计算机科学家在图论中一个传统的重要领域。在其中一些问题中，我将使用放电法——著名的四色问题最终在1979年被证明的工具。

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.