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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bollobás, B., Scott, A. D.: Judicious partitions of 3-uniform hypergraphs. Eur. J. Combinat., 21, 289–300 (2000)
Bollobás, B., Scott, A. D.: Judicious partitions of hypergraphs. J. Combin. Theory Ser. A, 78, 15–31 (1997)
Bollobás, B., Scott, A. D.: Problems and results on judicious partitions. Random Structures Algorithms, 21, 414–430 (2002)
Lee, C., Loh, P.-S., Sudakov, B.: Bisections of graphs. J. Combin. Theory Ser. B, 103(5), 599–629 (2013)
Ma, J., Yen, P. L., Yu, X. X.: On several partitioning problems of Bollobás and Scott. J. Combin. Theory Ser. B, 100(6), 631–649 (2010)
Poljak, S., Tuza, Z.: Maximum cuts and large bipartite subgraphs, in: Combinatorial Optimization, in: DIMACS Ser. Discrete Math. Theoret. Comput. Sci., American Mathematical Society, 1995
Shahrokhi, F., Székely, L. A.: The complexity of the bottleneck graph bipartition problem. J. Combin. Math. Combin. Comput., 15, 221–226 (1994)
Xu, B., Yan, J., Yu, X.: Balenced judicious bipartition of graphs. J. Graph Theory, 63, 210–225 (2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tang, Y.C., Xu, X. & Wang, G.H. Judicious bisection of hypergraphs. Acta. Math. Sin.-English Ser. 32, 579–584 (2016). https://doi.org/10.1007/s10114-016-4736-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10114-016-4736-8