{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,30]],"date-time":"2024-06-30T05:13:59Z","timestamp":1719724439325},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2010,6,9]],"date-time":"2010-06-09T00:00:00Z","timestamp":1276041600000},"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":[[2010,11]]},"abstract":"<jats:p>We investigate decompositions of a graph into a small number of low-diameter subgraphs. Let <jats:italic>P<\/jats:italic>(<jats:italic>n<\/jats:italic>, \u03b5, <jats:italic>d<\/jats:italic>) be the smallest <jats:italic>k<\/jats:italic> such that every graph <jats:italic>G<\/jats:italic> = (<jats:italic>V<\/jats:italic>, <jats:italic>E<\/jats:italic>) on <jats:italic>n<\/jats:italic> vertices has an edge partition <jats:italic>E<\/jats:italic> = <jats:italic>E<\/jats:italic><jats:sub>0<\/jats:sub> \u222a <jats:italic>E<\/jats:italic><jats:sub>1<\/jats:sub> \u222a \u22c5\u22c5\u22c5 \u222a <jats:italic>E<jats:sub>k<\/jats:sub><\/jats:italic> such that |<jats:italic>E<\/jats:italic><jats:sub>0<\/jats:sub>| \u2264 \u03b5<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>, and for all 1 \u2264 <jats:italic>i<\/jats:italic> \u2264 <jats:italic>k<\/jats:italic> the diameter of the subgraph spanned by <jats:italic>E<jats:sub>i<\/jats:sub><\/jats:italic> is at most <jats:italic>d<\/jats:italic>. Using Szemer\u00e9di's regularity lemma, Polcyn and Ruci\u0144ski showed that <jats:italic>P<\/jats:italic>(<jats:italic>n<\/jats:italic>, \u03b5, 4) is bounded above by a constant depending only on \u03b5. This shows that every dense graph can be partitioned into a small number of \u2018small worlds\u2019 provided that a few edges can be ignored. Improving on their result, we determine <jats:italic>P<\/jats:italic>(<jats:italic>n<\/jats:italic>, \u03b5, <jats:italic>d<\/jats:italic>) within an absolute constant factor, showing that <jats:italic>P<\/jats:italic>(<jats:italic>n<\/jats:italic>, \u03b5, 2) = \u0398(<jats:italic>n<\/jats:italic>) is unbounded for \u03b5 &lt; 1\/4, <jats:italic>P<\/jats:italic>(<jats:italic>n<\/jats:italic>, \u03b5, 3) = \u0398(1\/\u03b5<jats:sup>2<\/jats:sup>) for \u03b5 &gt; <jats:italic>n<\/jats:italic><jats:sup>\u22121\/2<\/jats:sup> and <jats:italic>P<\/jats:italic>(<jats:italic>n<\/jats:italic>, \u03b5, 4) = \u0398(1\/\u03b5) for \u03b5 &gt; <jats:italic>n<\/jats:italic><jats:sup>\u22121<\/jats:sup>. We also prove that if <jats:italic>G<\/jats:italic> has large minimum degree, <jats:italic>all the edges<\/jats:italic> of <jats:italic>G<\/jats:italic> can be covered by a small number of low-diameter subgraphs. Finally, we extend some of these results to hypergraphs, improving earlier work of Polcyn, R\u00f6dl, Ruci\u0144ski and Szemer\u00e9di.<\/jats:p>","DOI":"10.1017\/s0963548310000040","type":"journal-article","created":{"date-parts":[[2010,6,9]],"date-time":"2010-06-09T08:23:34Z","timestamp":1276071814000},"page":"753-774","source":"Crossref","is-referenced-by-count":3,"title":["Decompositions into Subgraphs of Small Diameter"],"prefix":"10.1017","volume":"19","author":[{"given":"JACOB","family":"FOX","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BENNY","family":"SUDAKOV","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,6,9]]},"reference":[{"key":"S0963548310000040_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190080408"},{"key":"S0963548310000040_ref3","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/s004930050035","article-title":"How to decrease the diameter of triangle-free graphs","volume":"18","author":"Erd\u0151s","year":"1998","journal-title":"Combinatorica"},{"key":"S0963548310000040_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(89)90066-X"},{"key":"S0963548310000040_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.12.002"},{"key":"S0963548310000040_ref6","first-page":"215","article-title":"On a problem of graph theory","volume":"1","author":"Erd\u0151s","year":"1966","journal-title":"Studia Scientarium Mathematicarum Hungar."},{"key":"S0963548310000040_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y"},{"key":"S0963548310000040_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02988307"},{"key":"S0963548310000040_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"S0963548310000040_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.11.023"},{"key":"S0963548310000040_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579292"},{"key":"S0963548310000040_ref8","unstructured":"[8] Hatami H. Graph norms and Sidorenko's conjecture. Israel J. Math., to appear."},{"key":"S0963548310000040_ref14","first-page":"419","volume-title":"Progress in Graph Theory","author":"Simonovits","year":"1984"},{"key":"S0963548310000040_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"S0963548310000040_ref5","first-page":"623","article-title":"On a problem in the theory of graphs (in Hungarian)","volume":"7","author":"Erd\u0151s","year":"1962","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T20:54:48Z","timestamp":1556398488000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000040\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,9]]},"references-count":14,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["S0963548310000040"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000040","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,9]]}}}