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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Sperner_family). Approximation algorithms for Generalizations are studied in [2]. 


**References**


[1](https://en.wikipedia.org/wiki/Sperner_family) 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



Lower bounds on size of unique cover?
Without loss of generality, there is no proper subfamily which still covers $U$. Then each set $S\_i$ contains an element $x\_i$ not covered by other sets $S\_j,j\ne i$. Take $V=\{x\_1,\dots,x\_m\}$, we have $|V|=m\geqslant n/k$. This is already better than $n/k^4$. 


Further $c\_1,c\_2,c\_3$ are some explicit constants. The above estimate may be improved to something like $c\cdot n/\log k$. Fo this, denote by $d\_i$ the number of sets in $S$ containing $e\_i$, without loss of generality we have $d\_1\leqslant d\_2\leqslant \dots \leqslant d\_n$. We have $\sum d\_i\leqslant mk\leqslant nk$, thus $d\_{n/2}\leqslant 2k$. Therefore we may find a set of indices $I\subset \{1,\dots,n/2\}$ such that $|I|\geqslant c\_1\cdot n/\log k$ and $d\_i\in [N,2N]$ for all $i\in I$ and suitable $N$. Denote $p=1/N$ and mark each index $j\in \{1,\dots,m\}$ with probability $p$. After that look at elements $e\_i\in U$ covered by exactly one marked set. They form our $V$. The expectation of the cardinality of $V$ is $\sum\_i d\_ip(1-p)^{d\_i-1}\geqslant c\_2\cdot |I|\geqslant c\_3\cdot n/\log k$. 


