4
$\begingroup$

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

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Do you have examples that are of size about $\frac{n}k?$ $\endgroup$ Commented Jun 16, 2017 at 4:03
  • $\begingroup$ @AaronMeyerowitz no, this may be improved, see update of my answer. But I still do not know about $c\cdot n$. I bet that this is not always achievable. $\endgroup$ Commented Jun 16, 2017 at 12:40
  • $\begingroup$ Do you have even one example where $|V| \le \frac{n}{2}?$ $\endgroup$ Commented Jun 17, 2017 at 7:12
  • $\begingroup$ Also:Let $U'$ be the union of the sets in $S'.$ I agree that we may assume that each subset in $S \setminus S'$ contains an element of $U \setminus U'$ not in any other member of $S.$ I also agree that we may assume that each subset in $A \in S'$ contains at least one element of $V$, i.e. not in any other member of $S'$ but don't see why we can assume $A$ contains an element not in any other member of $S$. $\endgroup$ Commented Jun 17, 2017 at 7:21
  • $\begingroup$ @AaronMeyerowitz If $A$ does not, remove $A$ from $S$ $\endgroup$ Commented Jun 17, 2017 at 8:01
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.