Extremal and stability results for graphs and hypergraphs

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

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.