{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T21:21:29Z","timestamp":1675804889836},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2011,2,9]],"date-time":"2011-02-09T00:00:00Z","timestamp":1297209600000},"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":[[2011,7]]},"abstract":"<jats:p>An <jats:italic>r<\/jats:italic>-cut of the complete <jats:italic>r<\/jats:italic>-uniform hypergraph <jats:italic>K<\/jats:italic><jats:sup><jats:italic>r<\/jats:italic><\/jats:sup><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is obtained by partitioning its vertex set into <jats:italic>r<\/jats:italic> parts and taking all edges that meet every part in exactly one vertex. In other words it is the edge set of a spanning complete <jats:italic>r<\/jats:italic>-partite subhypergraph of <jats:italic>K<\/jats:italic><jats:sup><jats:italic>r<\/jats:italic><\/jats:sup><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>. An <jats:italic>r<\/jats:italic>-cut cover is a collection of <jats:italic>r<\/jats:italic>-cuts such that each edge of <jats:italic>K<\/jats:italic><jats:sup><jats:italic>r<\/jats:italic><\/jats:sup><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is in at least one of the cuts. While in the graph case <jats:italic>r<\/jats:italic> = 2 any 2-cut cover on average covers each edge at least 2-<jats:italic>o<\/jats:italic>(1) times, when <jats:italic>r<\/jats:italic> is odd we exhibit an <jats:italic>r<\/jats:italic>-cut cover in which each edge is covered exactly once. When <jats:italic>r<\/jats:italic> is even no such decomposition can exist, but we can bound the average number of times an edge is cut in an <jats:italic>r<\/jats:italic>-cut cover between <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354831100006X_inline1\"><jats:alt-text>$1+\\frac1{r+1}$<\/jats:alt-text><\/jats:inline-graphic> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354831100006X_inline2\"><jats:alt-text>$1+\\frac{1+o(1)}{\\log r}$<\/jats:alt-text><\/jats:inline-graphic>. The upper bound construction can be reformulated in terms of a natural polyhedral problem or as a probability problem, and we solve the latter asymptotically.<\/jats:p>","DOI":"10.1017\/s096354831100006x","type":"journal-article","created":{"date-parts":[[2011,2,9]],"date-time":"2011-02-09T12:43:57Z","timestamp":1297255437000},"page":"519-527","source":"Crossref","is-referenced-by-count":3,"title":["Covering Complete <i>r<\/i>-Graphs with Spanning Complete <i>r<\/i>-Partite <i>r<\/i>-Graphs"],"prefix":"10.1017","volume":"20","author":[{"given":"SEBASTIAN M.","family":"CIOAB\u0102","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANDR\u00c9","family":"K\u00dcNDGEN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CRAIG M.","family":"TIMMONS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VLADISLAV V.","family":"VYSOTSKY","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,2,9]]},"reference":[{"key":"S096354831100006X_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2007.07.006"},{"key":"S096354831100006X_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00239-2"},{"key":"S096354831100006X_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010208"},{"key":"S096354831100006X_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1971.tb02618.x"},{"key":"S096354831100006X_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2009.02.007"},{"key":"S096354831100006X_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90045-0"},{"key":"S096354831100006X_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(89)90041-5"},{"key":"S096354831100006X_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199804)27:4<223::AID-JGT3>3.0.CO;2-P"},{"key":"S096354831100006X_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/0122040"},{"key":"S096354831100006X_ref13","volume-title":"A Second Course in Stochastic Processes","author":"Karlin","year":"1981"},{"key":"S096354831100006X_ref3","unstructured":"[3] Cioab\u0103 S. M. and K\u00fcndgen A. Covering hypergraphs with cuts of minimum total size. Graphs Combin. (to appear)."},{"key":"S096354831100006X_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1976.1084138"},{"key":"S096354831100006X_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001280"},{"key":"S096354831100006X_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788083"},{"key":"S096354831100006X_ref18","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1109\/SFCS.1982.80","article-title":"On the program size of perfect functions and universal hash functions","author":"Mehlhorn","year":"1982","journal-title":"Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science"},{"key":"S096354831100006X_ref9","first-page":"99","volume-title":"Lecture Notes in Mathematics","author":"Graham","year":"1972"},{"key":"S096354831100006X_ref21","volume-title":"Computational Mathematics, Modelling and Algorithms","author":"Radhakrishnan","year":"2001"},{"key":"S096354831100006X_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S096354831100006X_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/0605009"},{"key":"S096354831100006X_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90174-2"},{"key":"S096354831100006X_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.04.003"},{"key":"S096354831100006X_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00367-8"},{"key":"S096354831100006X_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060414"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831100006X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T07:57:12Z","timestamp":1556351832000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831100006X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,9]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["S096354831100006X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831100006x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,9]]}}}