Topical Studies in Graph and Matroid Theory

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

Graphs are mathematical abstractions which are used to model structures exhibiting a "discrete" nature. Examples include communication and transportation networks, crew scheduling, vehicle routing, computer chip design and digital devices. Matroids are structures which are more abstract than graphs, which are vital to the understanding of geometry, rigidity, and good algorithms for optimization problems. My research seeks to understand fundamental properties of such structures, with an aim toward optimizing various parameters of interest. For example, the problem of assigning shows to venues at a film festival can be modeled as a type of graph colouring problem. Advances in our knowledge can lead to improved scheduling algorithms. With the advent of digital communication such studies are vital to the efficient design and deployment of arising technologies. In more technical language, three of the projects comprising this proposal are as follows. - Few Long Lists for Edge Choosability: For graphs that can be embedded in the plane, the problem is to find a selection of colours for the edges, from preassigned lists, that avoid colour conflicts. - Colouring Oriented Matroids: The notion of graph colouring can be extended to geometric objects in two different ways. We compare properties of the two extensions, and the information that they carry. - Classification of Triangulated Surfaces with Few High-degree Vertices: Triangulated surfaces are central to computer rendering of surfaces. We investigate certain classes of such surfaces which deviate only slightly from canonical triangulations, where six edges meet at each vertex.