Packing and covering of graphs

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

Partitions and packings are central concepts in mathematics: How many prime factors does an integer have? How dense can balls be packed? Is a certain geometric shape suitable to tile the plane?This project deals with questions of this type arising in discrete mathematics. A graph is an object which consists of a (finite) set V of vertices and links between pairs of vertices (called edges). The question when a (large) graph G can be partitioned into a given family of small graphs is central in discrete mathematics and has already been investigated since the 19th century. There are numerous applications in statistical design theory, coding theory, and algebraic design theory. Recently, probabilistic methods have led to spectacular breakthroughs in this area. One aim of this project is to further develop these methods in order to gain partitions into sparse but very large graphs (such as spanning trees or unions of cycles). This is motivated for instance by the famous tree packing conjecture of Gyárfás and Lehel from 1976 and the Oberwolfach problem.Instead of asking for a (complete) partition into objects of a particular type, it is also very natural to ask for a maximal packing: How many objects with a certain property can be packed into a (large) different object? (For example: How many balls can be packed into a (large) box?) Such maximisation problems are frequently linked to a dual minimisation problem. This link is well-known in the context of linear optimisation. In graph theory, there is a link between a maximal packing and a minimal set of vertices which meet every copy of the packed graphs, that is, which cover these graphs. Another aim of this project is the investigation of this duality between packing and covering parameters in graphs; in particular, the Erdös-Pósa property of graph families.