Lower bounds on size of unique cover?

Question

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

Answer 1

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$.

Answer 2

I conjecture that there is always an $S'$ giving $|V|\ge \frac{k}{2k-1}n.$

A slightly weaker form which does not mention $k$ is:

Conjecture: One can always find an $S'$ giving $2|V| \gt n$

Here are some examples which achieve the first bound with equality. They all have $n=2k-1$ which seems rather small. However several disjoint copies can be combined to give a larger value of $n.$

Let $S$ be $k$ sets of size $k$ all sharing $k-1$ common points. Then $n=2k-1$ and taking $j \ge 2$ subsets for $S'$ gives $|V|=j.$ So taking either $j=1$ or $j=k$ gives $|V|=k.$ Take $t$ disjoint copies of this configuration to have $n=(2k-1)t$ and $|V|=kt.$

Here is another construction which seems to match, but not improve on, the one above when $k=2j$. So disjoint instances of both kinds could be mixed:

For $k=4$ let $S$ be $S_1\{{1,3,5,7\}},S_2\{{2,3,6,7\}},S_3=\{{4,5,6,7\}}.$ So $n=7.$ Then taking $S'$ to be any one or two of these gives $|V|=4.$

More generally, for $k=2^{i-1}$ let $U=\{{1,2,3,\cdots,2^i-1\}}$ and $S_j$ be the elements which have bit $j$ in their binary expansion equal to $1.$ Again, taking $S'$ to be any one or two of these gives $|V|=k.$

Even more generally, a symmetric $(4j-1,2j,j)$ design is a collection of $n=4j-1$ subsets (blocks) of an $n$ element set so that each block has size $k=2j$ (each object appears in $2j$ blocks) and an pair of subsets (pair of elements) intersect in $\lambda=j$ common points (occur in $j$ common blocks). These are conjectured to exist for all $j.$ The first open case is $j=117.$

Take $S$ to either be all the blocks or merely enough to cover all the objects. Again $n=2k-1$ and taking $S'$ to be any one or two blocks gives $|V|=k.$

A final example for $k=5$ and $n=9$ is

$\{{1,2,3,4,5\}},\{{1,2,3,4,6\}},\{{1,2,3,4,7\}},\{{1,2,3,8,9\}}.$