Given a universe $U = \{e_1 , . . . , e_n\}$ of elements, and given a collection $S = \{S_1 , . . . , S_m \}$ of subsets of $U$, each of size $\le k$, the subcollection $S' \subseteq S$ is a unique coverage of $V \subseteq U$ if each $e \in V$ is uniquely covered, i.e., appears in exactly one set of $S'$. For simplicity, we assume that $\cup {S_i}=U$.

Question: Give a lowerbound on the maximum size of $V$, as a function $f(n, k)$.

Notice that here we are not interested in computational and algorithmic aspects. I think I can come up with a $n/k^4$ lowerbound (and constructive).

Background

The problem of maximizing the unique cover for $k \ge 3$ is NP-hard. The approximation algorithms are studied in [1]. Approximation algorithms for Generalizations are studied in [2].

References

[1] V. Guruswami and L. Trevisan, The complexity of making unique choices: Approximating 1-in-k SAT, 2005.

[2] ERIK D. DEMAINE , URIEL FEIGE , et al, Combination can be hard: Approximability of the unique coverage problem

Given a universe $U = \{e_1 , . . . , e_n\}$ of elements, and given a collection $S = \{S_1 , . . . , S_m \}$ of subsets of $U$, each of size $\le k$, the subcollection $S' \subseteq S$ is a unique coverage of $V \subseteq U$ if each $e \in V$ is uniquely covered, i.e., appears in exactly one set of $S'$. For simplicity, we assume that $\cup {S_i}=U$.

Question 1: Give a lowerbound on the maximum size of $V$, as a function $f(n, k)$.

Question 2: Does it help if $S$ is a Sperner family?

Notice that here we are not interested in computational and algorithmic aspects. I think I can come up with a $n/k^4$ lowerbound (and constructive).

Background

The problem of maximizing the unique cover for $k \ge 3$ is NP-hard. The approximation algorithms are studied in 1. Approximation algorithms for Generalizations are studied in [2].

References

1 V. Guruswami and L. Trevisan, The complexity of making unique choices: Approximating 1-in-k SAT, 2005.

[2] ERIK D. DEMAINE , URIEL FEIGE , et al, Combination can be hard: Approximability of the unique coverage problem