Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-04T19:45:06.405Z Has data issue: false hasContentIssue false
  • English
  • Français

Generating All Sets With Bounded Unions

Published online by Cambridge University Press:  01 September 2008

YANNICK FREIN ,
BENJAMIN LÉVÊQUE  and
ANDRÁS SEBŐ
YANNICK FREIN
Affiliation:
Laboratoire G-SCOP, INPG, UJF, CNRS, 46, avenue Felix Viallet, 38031 Grenoble Cedex, France (e-mail: [email protected])
BENJAMIN LÉVÊQUE
Affiliation:
Laboratoire G-SCOP, INPG, UJF, CNRS, 46, avenue Felix Viallet, 38031 Grenoble Cedex, France (e-mail: [email protected])
ANDRÁS SEBŐ
Affiliation:
Laboratoire G-SCOP, INPG, UJF, CNRS, 46, avenue Felix Viallet, 38031 Grenoble Cedex, France (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 5 , September 2008 , pp. 641 - 660
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[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.)Google Scholar
[2]Erdős, P. (1993) Private communication mentioned in [3].Google Scholar
[3]Füredi, Z. and Katona, G. O. H. (2006) 2-bases of quadruples. Combin. Probab. Comput. 15 131–141.CrossRefGoogle Scholar
[4]Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman.Google Scholar
[5]Sidorenko, A. F. (1995) What we know and what we do not know about Turán numbers. Graphs Combin. 11 179–199.CrossRefGoogle Scholar
[6]Turán, P. (1941) On an extremal problem in graph theory. Math. Fiz. Lapok 48 436–452. (In Hungarian.)Google Scholar