Judicious bisection of hypergraphs |
| |
Authors: | Yu Cong Tang Xin Xu Guang Hui Wang |
| |
Institution: | 1.Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, P. R. China;2.School of Mathematics, Shandong University, Ji'nan 250100, P. R. China |
| |
Abstract: | Judicious bisection of hypergraphs asks for a balanced bipartition of the vertex set that optimizes several quantities simultaneously. In this paper, we prove that if G is a hypergraph with n vertices and m i edges of size i for i = 1, 2, …, k, then G admits a bisection in which each vertex class spans at most \(\frac{{m1}}{2} + \frac{1}{4}{m_2} + \cdots + \left( {\frac{1}{{{2^k}}}} \right){m_k} + o\left( {{m_1} + \cdots + {m_k}} \right)\) edges, where G is dense enough or Δ(G) = o(n) but has no isolated vertex, which turns out to be a bisection version of a conjecture proposed by Bollobás and Scott. |
| |
Keywords: | Partition judicious bisection hypergraph |
本文献已被 CNKI SpringerLink 等数据库收录! |
| 点击此处可从《数学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《数学学报(英文版)》下载免费的PDF全文 |
|