Matchings and tilings in graphs

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

Graph theory concerns the mathematical study of networks (such as computer networks, social networks and biological networks). Graphs consist of a set of vertices and a set of edges connecting some pairs of these vertices. In a real-world network it is often important to pair off resources. For example, one might wish to assign workers to different tasks, or donors to suitable patients. In the graph setting, these are examples of matching problems (a matching is a collection of disjoint edges in a graph). A perfect matching in a graph is a collection of disjoint edges that cover all the vertices in the graph. Perfect matchings in graphs are well-understood in the sense that one can efficiently determine (via an algorithm of Edmonds) whether a graph contains a perfect matching.It is also natural to consider generalisations of the notion of a matching. For example, one may seek to split a workforce into collections of teams of a given size. This is an example of a perfect tiling problem in a graph. Alternatively, one may wish to assign employees to specific jobs based in various different locations. This is an example of a perfect matching problem in a 3-partite 3-graph (i.e. now edges consist of three, not two vertices). In stark contrast to perfect matchings in graphs, it is believed that there is no efficient algorithm for finding such perfect tilings in graphs, nor for finding perfect matchings in 3-graphs (and more generally in k-graphs for any whole number at least 3). Indeed, these are examples of NP-complete problems; so finding such efficient algorithms would resolve one of the Millennium Prize Problems.As such, an emergent research direction is to find general conditions that force a k-graph to contain a perfect matching, or force a graph to contain a perfect tiling. Underlying this approach are methods that often centre on the random-like behaviour of dense graphs and k-graphs.There are two key goals underpinning the research proposal. First, the project focuses on finding general classes of k-graphs where one can efficiently determine whether the k-graph contains a perfect matching. Second, we will investigate sufficient conditions that force a perfect tiling, as well as establishing how far away graphs of a given density can be from containing a perfect tiling. In particular, we will study perfect tilings in vertex ordered graphs (i.e. the vertices now have some given ordering). Unfortunately, some of the key random-like properties of dense graphs do not extend to vertex ordered graphs. Thus, an aim of the project is to develop novel approaches that will in turn give us a better understanding of such properties in the ordered setting.