Extremal and stability results for graphs and hypergraphs

图是由一组顶点和一组边组成的抽象构型，其中每条边都是大小为2的顶点集的子集。除了边可以有任意大小之外，超图类似。许多现实世界的现象都可以建模为图或超图，对图和超图理论的贡献可以有重要的实际应用，例如在通信或电力系统网络的效率和可靠性方面。*我的研究是图和超图的极值问题。一般的极值问题是根据一个参数最大化或最小化另一个参数(或其他参数)。例如，自然图参数是最大度，即包含任何给定顶点的最大边数。这里有一个典型的极值问题：什么是最小的M，使得一个最大度为d的图G的每个顶点划分成至少M个大小的类包含一个独立的横截(在每一类中选择一个顶点，使得G的任何边都不连接任何两个选定的顶点)？在数学和计算机科学中，这个非常普遍的问题出现在许多不同的环境中。我在几年前的工作中回答了这个问题，表明M=2d是正确的值。此外，这是最有可能的，因为存在没有独立横截的划分类大小为2d-1的图(对于该问题，这样的图称为极值图)。这个定理现在被许多作者应用于图论(包括图着色的许多不同方面)、超图匹配、群论、环论和计算机科学中的资源分配问题。与任何极值问题有关的一个重要问题是所谓的稳定性版本：如果给定图G的所选参数接近最大(或最小)可能值，则G的结构是否接近极值配置？极值定理的稳定性版本的重要性体现在它的应用中：在应用中，如果一个人知道所涉及的图的结构信息，表明它们不接近极值例子，那么将产生更好的界。*我提出的研究的主要目的之一是获得图和超图中某些极值问题的稳定性版本，例如上面描述的那个。由于我打算解决的结果的大量现有应用程序，稳定性版本将在许多领域产生重大影响。*我目前研究的其他方面与应用程序更直接相关。例如，我曾与一个电力系统工程师团队合作，在安大略省新的智能电网的背景下使用图论对供电网络进行高效建模，我希望与这个团队继续进行类似的项目。我和计算机科学的同事一起开发了变形平面图形的算法，这是计算机动画、医学成像和运动规划中出现的一个问题。

A graph is an abstract configuration consisting of a set of vertices and a set of edges, where each edge is a subset of the vertex set of size two. A hypergraph is similar except that edges can have any size. Many real-world phenomena can be modelled as graphs or hypergraphs, and contributions to the theory of graphs and hypergraphs can have important practical applications, for example in efficiency and reliability of communication or power systems networks.******My research is in extremal problems for graphs and hypergraphs. The general extremal problem is to maximize or minimize one parameter in terms of another (or others). For example, a natural graph parameter is the maximum degree, the largest number of edges containing any given vertex. Here is a typical extremal question: what is the smallest M such that every vertex partition of a graph G with maximum degree d into classes of size at least M contains an independent transversal (a choice of one vertex in each class such that no edge of G joins any two chosen vertices)? This very general problem comes up in many different settings in mathematics and computer science. I answered it in my work some years ago, showing that M=2d is the correct value. Moreover this is best possible, in that there exist graphs with partition class size 2d-1 that do not have independent transversals (such graphs are called extremal for the problem). This theorem now has many applications by various authors, to results in graph theory (including many different aspects of graph colouring), hypergraph matching, group theory, ring theory and resource allocation problems in computer science.******An important problem associated with any extremal question is the so-called stability version: if the chosen parameter of a given graph G is close to the maximum (or minimum) possible value, is the structure of G close to that of an extremal configuration? The significance of the stability version of an extremal theorem is seen in its applications: if in an application one knows structural information about the graphs involved that shows they are not close to extremal examples, then improved bounds will result.******One of the main aims of my proposed research is to obtain stability versions of certain extremal problems in graphs and hypergraphs, e.g. the one described above. Because of the large number of existing applications of the results I intend to address, stability versions would have significant impact in many areas.******Other aspects of my current research are more directly tied to applications. For example, I have worked with a team of power systems engineers on using graph theory for efficient modelling of power supply networks in the setting of the new Smart Grid in Ontario, and I expect to continue on similar projects with this same team. With colleagues in computer science I have developed algorithms for morphing planar graphs, a problem that arises in computer animation, medical imaging and motion planning.