Judicious partitions of weighted hypergraphs
2016
Let G be a weighted hypergraph with edges of size i for i = 1, 2. Let wi denote the total weight of edges of size i and a be the maximum weight of an edge of size 1. We study the following partitioning problem of Bollobas and Scott: Does there exist a bipartition such that each class meets edges of total weight at least \ \(frac{{w1 - \alpha }}{2} + \frac{{2w2}}{3}\)? We provide an optimal bound for balanced bipartition of weighted hypergraphs, partially establishing this conjecture. For dense graphs, we also give a result for partitions into more than two classes. In particular, it is shown that any graph G with m edges has a partition V1,...,Vk such that each vertex set meets at least \(\left( {1 - \left( {1 - \tfrac{1} {k}} \right)^2 } \right)m + o(m)\) edges, which answers a related question of Bollobas and Scott.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
27
References
2
Citations
NaN
KQI