Judicious partitions of weighted hypergraphs
详细信息 查看全文
- 作者：Xin Xu ; GuiYing Yan ; Yao Zhang
- 关键词：judicious partition ; balanced bipartition ; weighted hypergraph ; 05C15
- 刊名：SCIENCE CHINA Mathematics
- 出版年：2016
- 出版时间：March 2016
- 年：2016
- 卷：59
- 期：3
- 页码：609-616
- 全文大小：247 KB
- 参考文献：1.Bollobás B, Scott A D. Judicious partitions of graphs. Period Math Hungar, 1993, 26: 125–137CrossRef MathSciNet
2.Bollobás B, Scott A D. Exact bounds for judicious partitions of graphs. Combinatorica, 1999, 19: 473–486CrossRef MathSciNet
3.Bollobás B, Scott A D. Judicious partitions of 3-uniform hypergraphs. Eur J Combinat, 2000, 21: 289–300CrossRef
4.Bollobás B, Scott A D. Problems and results on judicious partitions. Random Structures Algorithms, 2002, 21: 414–430CrossRef MathSciNet
5.Bollobás B, Scott A D. Judicious partitions of bounded-degree graphs. J Graph Theory, 2004, 46: 131–143CrossRef MathSciNet
6.Edwards C S. Some extremal properties of bipartite graphs. Canad J Math, 1973, 25: 475–485CrossRef MathSciNet
7.Edwards C S. An improved lower bound for the number of edges in a largest bipartite subgraph. In: Proceedings of the 2nd Czechoslovak Symposium on Graph Theory. Prague: Academia, 1975, 167–181
8.Haslegrave J. The Bollobás-Thomason conjecture for 3-uniform hypergraphs. Combinatorica, 2012, 32: 451–471CrossRef MathSciNet
9.Janson S, Luczak T, Ruci´nski A. Random Graphs. New York: Wiley, 2000CrossRef
10.Karp R M. Reducibility among combinatorial problems. In: Complexity of Computer Computations. New York: Plenum Press, 1972, 85–103CrossRef
11.Ma J, Yen P, Yu X. On several partitioning problems of Bollobás and Scott. J Combin Theory Ser B, 2010, 100: 631–649CrossRef MathSciNet
12.Porter T D. On a bottleneck bipartition conjecture of Erd¨os. Combinatorica, 1992, 12: 317–321CrossRef MathSciNet
13.Scott A D. Judicious partitions and related problems. In: Surveys in Combinatorics. London Math Soc Lecture Notes Ser, vol. 327. Cambridge: Cambridge University Press, 2005, 95–117
14.Xu B, Yan J, Yu X. Balanced judicious partitions of graphs. J Graph Theory, 2010, 63: 210–225MathSciNet
15.Xu B, Yan J, Yu X. A note on balanced bipartitions. Discrete Math, 2010, 310: 2613–2617MathSciNet
16.Xu B, Yu X. Judicious k-partitions of graphs. J Combin Theory Ser B, 2009, 99: 324–337CrossRef MathSciNet
17.Xu B, Yu X. Better bounds for k-partitions of graphs. Combinatorics. Probab Comput, 2011, 20: 631–640CrossRef MathSciNet
18.Xu B, Yu X. On judicious bisections of graphs. J Combin Theory Ser B, 2014, 106: 30–69CrossRef MathSciNet - 作者单位：Xin Xu (1)
GuiYing Yan (1)
Yao Zhang (1)
1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, China - 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Chinese Library of Science
Applications of Mathematics - 出版者：Science China Press, co-published with Springer
- ISSN：1869-1862
文摘
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 Bollobás 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,...,V k 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 Bollobás and Scott. Keywords judicious partition balanced bipartition weighted hypergraph