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.