Transversals, colouring, matchings and covers

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

The objectives of my research will be to solve various extremal-type problems in graphs and hypergraphs. A hypergraph H is an abstract object consisting of a set of vertices V and a set of hyperedges E such that each element of E is a subset of V. A graph is just a hypergraph in which every (hyper)edge has size 2. Many important problems, both theoretical and practical, can be expressed in terms of basic questions about graphs or hypergraphs. The problems I will address can all be stated in this purely abstract terminology, and usually involve partitions with certain special properties. However in many cases they come from very concrete problems. Two specific applications I have worked on recently involve effective routing protocols in the internet, and the development of effective schemes for performing automatic fault restoration in electrical power systems. Fault restoration is the process of restoring power in an electrical grid by reconfiguring the network, after a power failure caused by a storm or other accidental damage to power lines or other components of the network. With the development of the smart grid, the need for automation in power restoration and other aspects of network operation is becoming much greater.