Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T06:35:27.080Z Has data issue: false hasContentIssue false

Generating All Sets With Bounded Unions

Published online by Cambridge University Press:  01 September 2008

YANNICK FREIN
Affiliation:
Laboratoire G-SCOP, INPG, UJF, CNRS, 46, avenue Felix Viallet, 38031 Grenoble Cedex, France (e-mail: yannick.frein.benjamin.leveque.andras.sebo@g-scop.inpg.fr)
BENJAMIN LÉVÊQUE
Affiliation:
Laboratoire G-SCOP, INPG, UJF, CNRS, 46, avenue Felix Viallet, 38031 Grenoble Cedex, France (e-mail: yannick.frein.benjamin.leveque.andras.sebo@g-scop.inpg.fr)
ANDRÁS SEBŐ
Affiliation:
Laboratoire G-SCOP, INPG, UJF, CNRS, 46, avenue Felix Viallet, 38031 Grenoble Cedex, France (e-mail: yannick.frein.benjamin.leveque.andras.sebo@g-scop.inpg.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2008