{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:47:52Z","timestamp":1759063672088},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T00:00:00Z","timestamp":1471305600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2017,3]]},"abstract":"<jats:p>Judicious partitioning problems on graphs and hypergraphs ask for partitions that optimize several quantities simultaneously. Let <jats:italic>k<\/jats:italic> \u2265 2 be an integer and let <jats:italic>G<\/jats:italic> be a hypergraph with <jats:italic>m<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> edges of size <jats:italic>i<\/jats:italic> for <jats:italic>i<\/jats:italic>=1,2. Bollob\u00e1s and Scott conjectured that <jats:italic>G<\/jats:italic> has a partition into <jats:italic>k<\/jats:italic> classes, each of which contains at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000274_inline1\" \/><jats:tex-math>$m_1\/k+m_2\/k^2+O(\\sqrt{m_1+m_2})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> edges. In this paper, we confirm the conjecture affirmatively by showing that <jats:italic>G<\/jats:italic> has a partition into <jats:italic>k<\/jats:italic> classes, each of which contains at most\n<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548316000274_eqnU1\" \/><jats:tex-math>$$m_1\/k+m_2\/k^2+\\ffrac{k-1}{2k^2}\\sqrt{2(km_1+m_2)}+O(1)$$.<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>\nedges. This bound is tight up to <jats:italic>O<\/jats:italic>(1).<\/jats:p>","DOI":"10.1017\/s0963548316000274","type":"journal-article","created":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T07:01:08Z","timestamp":1471330868000},"page":"267-284","source":"Crossref","is-referenced-by-count":8,"title":["Judicious Partitioning of Hypergraphs with Edges of Size at Most 2"],"prefix":"10.1017","volume":"26","author":[{"given":"JIANFENG","family":"HOU","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"QINGHOU","family":"ZENG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,8,16]]},"reference":[{"key":"S0963548316000274_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.06.002"},{"key":"S0963548316000274_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00036-4"},{"key":"S0963548316000274_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.04.004"},{"key":"S0963548316000274_ref10","unstructured":"Edwards C. S. (1975) An improved lower bound for the number of edges in a largest bipartite subgraph. In Proc. 2nd Czechoslovak Symposium on Graph Theory, pp. 167\u2013181."},{"key":"S0963548316000274_ref5","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1998.0266"},{"key":"S0963548316000274_ref6","unstructured":"Bollob\u00e1s B. and Scott A. D. (2002) Better bounds for Max Cut. In Contemporary Combinatorics, Vol. 10 of Bolyai Society Mathematical Studies, pp. 185\u2013246."},{"key":"S0963548316000274_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2916-7"},{"key":"S0963548316000274_ref11","doi-asserted-by":"crossref","unstructured":"Fan G. and Hou J. Bounds for pairs in judicious partitions of graphs. Random Struct. Alg. doi:10.1002\/rsa.20642","DOI":"10.1002\/rsa.20642"},{"key":"S0963548316000274_ref3","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1996.2744"},{"key":"S0963548316000274_ref9","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1973-048-x"},{"key":"S0963548316000274_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2696-x"},{"key":"S0963548316000274_ref19","first-page":"95","volume-title":"Surveys in Combinatorics","author":"Scott","year":"2005"},{"key":"S0963548316000274_ref22","doi-asserted-by":"crossref","unstructured":"Yannakakis M. (1978) Node- and edge-deletion NP-complete problems. In STOC '78: Proc. 10th Annual ACM Symposium on Theory of Computing, pp. 253\u2013264.","DOI":"10.1145\/800133.804355"},{"key":"S0963548316000274_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.07.001"},{"key":"S0963548316000274_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.07.007"},{"key":"S0963548316000274_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.09.001"},{"key":"S0963548316000274_ref4","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/s004939970002","article-title":"Exact bounds for judicious partitions of graphs","volume":"19","author":"Bollob\u00e1s","year":"1999","journal-title":"Combinatorica"},{"key":"S0963548316000274_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.06.002"},{"key":"S0963548316000274_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2016.02.004"},{"key":"S0963548316000274_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10062"},{"key":"S0963548316000274_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.01.004"},{"key":"S0963548316000274_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.07.002"},{"key":"S0963548316000274_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261315"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548316000274","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T22:10:03Z","timestamp":1555539003000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548316000274\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,16]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["S0963548316000274"],"URL":"https:\/\/doi.org\/10.1017\/s0963548316000274","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,16]]}}}