{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T04:01:27Z","timestamp":1750564887722,"version":"3.41.0"},"reference-count":6,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T00:00:00Z","timestamp":1220227200000},"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":[[2008,9]]},"abstract":"<jats:p>We consider the problem of minimizing the size of a family of sets <jats:private-char>\n\t      <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830800922X_char1\"\/>\n\t    <\/jats:private-char> such that every subset of {1,.\u00a0.\u00a0., <jats:italic>n<\/jats:italic>} can be written as a disjoint union of at most <jats:italic>k<\/jats:italic> members of <jats:private-char>\n\t      <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830800922X_char1\"\/>\n\t    <\/jats:private-char>, where <jats:italic>k<\/jats:italic> and <jats:italic>n<\/jats:italic> are given numbers. This problem originates in a real-world application aiming at the diversity of industrial production. At the same time, the question of finding the minimum of |<jats:private-char>\n\t      <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830800922X_char1\"\/>\n\t    <\/jats:private-char>| so that every subset of {1,.\u00a0.\u00a0., <jats:italic>n<\/jats:italic>} is the union of two sets in <jats:private-char>\n\t      <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354830800922X_char1\"\/>\n\t    <\/jats:private-char> was asked by Erd\u0151s and studied recently by F\u00fcredi and Katona without requiring the disjointness of the sets. A simple construction providing a feasible solution is conjectured to be optimal for this problem for all values of <jats:italic>n<\/jats:italic> and <jats:italic>k<\/jats:italic> and regardless of the disjointness requirement; we prove this conjecture in special cases including all (<jats:italic>n<\/jats:italic>, <jats:italic>k<\/jats:italic>) for which <jats:italic>n<\/jats:italic>\u22643<jats:italic>k<\/jats:italic> holds, and some individual values of <jats:italic>n<\/jats:italic> and <jats:italic>k<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s096354830800922x","type":"journal-article","created":{"date-parts":[[2008,7,8]],"date-time":"2008-07-08T09:19:30Z","timestamp":1215508770000},"page":"641-660","source":"Crossref","is-referenced-by-count":2,"title":["Generating All Sets With Bounded Unions"],"prefix":"10.1017","volume":"17","author":[{"given":"YANNICK","family":"FREIN","sequence":"first","affiliation":[]},{"given":"BENJAMIN","family":"L\u00c9V\u00caQUE","sequence":"additional","affiliation":[]},{"given":"ANDR\u00c1S","family":"SEB\u0150","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,9,1]]},"reference":[{"key":"S096354830800922X_manual_ref-4","unstructured":"[4] Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman."},{"key":"S096354830800922X_manual_ref-6","first-page":"436","article-title":"On an extremal problem in graph theory","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Math. Fiz. Lapok"},{"key":"S096354830800922X_manual_ref-5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01929486"},{"key":"S096354830800922X_manual_ref-3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007248"},{"key":"S096354830800922X_manual_ref-1","unstructured":"[1] Da Cunha, C. (2004) Definition and inventory management of semi-finished products in an Assembly To Order context. PhD Thesis, INPG, Grenoble. (In French.)"},{"key":"S096354830800922X_manual_ref-2","unstructured":"[2] Erd\u0151s, P. (1993) Private communication mentioned in [3]."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354830800922X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T03:17:38Z","timestamp":1750475858000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354830800922X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":6,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["S096354830800922X"],"URL":"https:\/\/doi.org\/10.1017\/s096354830800922x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2008,9]]}}}