报告题目：Several problems on judicious partitions of graphs and hypergraphs

报告人：Jianfeng Hou      Center for Discrete Mathematics, Fuzhou University

报告时间：12月4日（周五）3：15-4：15

报告地点：1518

摘要：

Many classical partition problems in Combinatorics and Computer Science seek a partition of a combinatorial object (e.g., a graph, directed graph, hypergraph, etc.) which optimizes 

a single parameter. One such problem are the MaxCut problem, where one seeks to partition the vertex set V (G) of a graph G into two disjoint parts V 1 and V 2 so that the number 

of edges of G crossing between V 1 and V 2 is maximal. Judicious partition problem is to partition the vertex set of a graph or hypergraph such that several quantities are optimized 

simultaneously. 

In 2002, Bollobás and Scott studied the graph and hypergraph partition problems from several different angles and proposed many problems. In this talk, we will investigate some 

of them through combinatorial and probabilistic arguments.

Keywords: graph, hypergraph, Max-Cut problem, judicious partition