Loading...
Please wait, while we are loading the content...
Similar Documents
Generating All Sets With Bounded Unions
| Content Provider | Scilit |
|---|---|
| Author | Frein, Yannick Lévêque, Benjamin Sebő, András |
| Copyright Year | 2008 |
| Description | We consider the problem of minimizing the size of a family of sets such that every subset of {1,. . ., n} can be written as a disjoint union of at most k members of , where k and n 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 || so that every subset of {1,. . ., n} is the union of two sets in was asked by Erdős and studied recently by Füredi 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 n and k and regardless of the disjointness requirement; we prove this conjecture in special cases including all (n, k) for which n≤3k holds, and some individual values of n and k. |
| Related Links | https://hal.archives-ouvertes.fr/hal-00189041/file/Diversity.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/0978B3363E223E29CF8704A185EDE55F/S096354830800922Xa.pdf/div-class-title-generating-all-sets-with-bounded-unions-div.pdf |
| Ending Page | 660 |
| Page Count | 20 |
| Starting Page | 641 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s096354830800922x |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 05 |
| Volume Number | 17 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2008-09-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
