Abstract
The vertices of any graph with m edges may be partitioned into two parts so that each part meets at least \(\tfrac{{2m}} {3}\) edges. Bollobás and Thomason conjectured that the vertices of any r-uniform hypergraph with m edges may likewise be partitioned into r classes such that each part meets at least \(\tfrac{r} {{2r - 1}}\) edges. In this paper we prove the weaker statement that, for each r ≥ 4, a partition into r classes may be found in which each class meets at least \(\tfrac{r} {{3r - 4}}\) edges, a substantial improvement on previous bounds.
Similar content being viewed by others
References
N. Alon and E. Halperin: Bipartite subgraphs of integer weighted graphs, Discrete Math. 181 (1998), 19–29.
B. Bollobás: Modern Graph Theory, Graduate Texts in Mathematics 184, Springer-Verlag, New York, 1998. xiv+394 pp.
B. Bollobás, B. Reed and A. Thomason: An extremal function for the achromatic number, in: Graph Structure Theory (Seattle, WA, 1991), 161–165, Contemp. Math. 147, Amer. Math. Soc., Providence, RI, 1993.
B. Bollobás and A.D. Scott: On judicious partitions of graphs, Period. Math. Hungar. 26 (1993), 127–139.
B. Bollobás and A.D. Scott: Judicious partitions of hypergraphs, J. Combin. Theory Ser. A 78 (1997), 15–31.
B. Bollobás and A. D. Scott: Exact bounds for judicious partitions of graphs, Combinatorica 19 (1999), 473–486.
B. Bollobás and A.D. Scott: Judicious partitions of 3-uniform hypergraphs, European J. Combin. 21 (2000), 289–300.
B. Bollobás and A.D. Scott: Problems and results on judicious partitions, Random Structures Algorithms 21 (2002), 414–430.
B. Bollobás and A.D. Scott: Better bounds for Max Cut, in: Contemporary Combinatorics, Bolyai Soc. Math. Stud. 10 (2002), 185–246.
J. Haslegrave: The Bollobás-Thomason conjecture for 3-uniform hypergraphs, Combinatorica 32 (2012), 451–471.
T. D. Porter: On a bottleneck bipartition conjecture of Erdős, Combinatorica 12 (1992), 317–321.
T. D. Porter and Bing Yang: Graph partitions II, J. Combin. Math. Combin. Comput. 37 (2001), 149–158.
A. D. Scott: Judicious partitions and related problems, in: Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Ser., 327, Cambridge Univ. Press, Cambridge, 2005, 95–117.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by the Engineering and Physical Sciences Research Council.
Rights and permissions
About this article
Cite this article
Haslegrave, J. Judicious partitions of uniform hypergraphs. Combinatorica 34, 561–572 (2014). https://doi.org/10.1007/s00493-014-2916-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-014-2916-7