概率方法在超图与有向图划分中的应用

Graph partitions is one of the most important topics in both Combinatorics and Theoretical Computer Science. It has important applications in many scientific and engineering fields such as complex network structure analysis and large-scale integrated circuit physical design. Partitioning problems for general graphs has been studied extensively and with a wealth of results. For the lake of effective tools, the study of hypergraphs and directed graphs is still lag behind. There are still many problems to be solved. The probabilistic method is one of the most powerful and widely used tools applied in Combinatorics. However, there are few people in our country who are engaged in the study of graph partitions through using the probabilistic method. In this project, we will work on the following partitioning problems of hypergraphs and directed graphs by using the probabilistic method: (1) k-partitions of r-uniform hypergraphs that maximum the number of edges incident with each set; (2) Bipartitions of mixed hypergraphs that maximum the number of edges incident with each set; (3) Bipartitions of directed graphs which maximum the number of the directed cut for each direction. Our goal is to give some new ideas for these problems and hope to solve them through using the probabilistic method. On one hand, this research can help to better understand the structural nature of hypergraphs and directed graphs. On the other hand, the research may provide theoretical support for some engineering problems such as integrated circuit design.

图划分理论是组合数学与理论计算机科学领域中的重要研究课题之一，它在复杂网络社团结构分析、大规模集成电路物理设计等科学与工程领域都有重要应用。目前划分问题对于一般图已有广泛的研究，但作为推广的超图与有向图的划分却因缺乏有效的处理工具而进展不多，尚有许多问题急需解决。概率方法是组合数学中最有效和最广为使用的工具之一，目前国内利用概率方法从事图划分问题研究的人并不多，本项目将利用概率方法来研究超图与有向图中的下述划分问题：(1)r一致超图k部划分要求每部分关联边数都尽量多；(2)混合超图二部划分要求每部分关联边数都尽量多；(3)有向图二部划分要求两个方向有向边割都尽量大。目标是通过概率工具给出超图与有向图划分研究的新思路，从而解决以上问题。通过本项目的研究，一方面可以帮助更好理解超图有向图的结构性质，另一方面能为集成电路设计等工程问题提供有效的理论支持。

图划分理论是图论领域中的重要研究课题之一，作为一类典型的组合优化问题出现在大量的科学与工程实际之中。利用概率方法对图划分领域中几个热点、难点问题进行了研究。(1) 研究了有向图公平二部划分问题。围绕Hou, Wu关于有向图二部划分的猜想,证明了猜想对最小半度不超过3的有向图是成立的。围绕Lee，Loh与Sudakov的猜想，给出了猜想成立的两个图类。(2) 研究了Bollobás与Scott提出的在平衡划分下求最大割或最小割的问题。对于最大平衡二划分，我们给出了大小至少为m/2+cn（c>0为常数）的平衡二划分存在的一个充分条件。对于最小平衡二划分，我们给出了大小至多为m/2-cn（c>0为常数）的平衡二划分存在的一些充分条件。(3) 研究了Bollobás与Scott提出的图的公平平衡划分问题：在什么条件下，一个m条边的图会存在平衡二划分，满足划分所得每部分点集诱导出至多m/4+o(m)条边？我们给出了结论成立的一个充分条件。项目研究丰富了结构图论与极值图论的基础理论，对复杂网络社团结构分析、大规模集成电路物理设计等科学与工程问题提供有效的理论支持。研究成果发表在European Journal of Combinatorics、Journal of Graph Theory等专业期刊。