权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Packing and covering of graphs

图的包装和覆盖

基本信息

批准号：
339933727
负责人：
Professor Dr. Felix Joos
金额：
--
依托单位：
Arbeitsgruppe Theoretische Informatik
依托单位国家：
德国
项目类别：
Research Fellowships
财政年份：
2017
资助国家：
德国
起止时间：
2016-12-31 至 2018-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/339933727?language=en
关键词：
Packing covering 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.

划分和填充是数学中的核心概念：一个整数有多少个素因数？球的密度可以有多大？某一几何形状适合于平铺平面吗？本课题研究的是离散数学中出现的这类问题。图是由(有限的)顶点集合V和顶点对之间的链接(称为边)组成的对象。一个(大)图G何时可以划分成一个给定的小图族的问题是离散数学的核心问题，自19世纪以来一直被研究。在统计设计理论、编码理论和代数设计理论中有着广泛的应用。最近，概率方法在这一领域取得了惊人的突破。这个项目的一个目标是进一步开发这些方法，以便将分区划分成稀疏但非常大的图(如生成树或圈的并)。这是由著名的树包装猜想和Oberwolfach问题引起的，例如1976年S和Lehel的树包装猜想。与其要求将(完全)划分为特定类型的对象，要求最大填充也是非常自然的：有多少具有某种性质的对象可以被包装成(大)不同的对象？(例如：一个(大)盒子可以装多少球？)这样的最大化问题经常与对偶最小化问题联系在一起。在线性优化的背景下，这种联系是众所周知的。在图论中，最大填充和满足每个压缩图副本的最小顶点集之间存在联系，也就是说，覆盖这些图。这个项目的另一个目的是研究图中填充参数和覆盖参数之间的对偶性，特别是图族的ErdöS-Pósa性质。