Unique coverage

118 Views Asked by At

Given a collection $A$ of $m$ sets $S_1,\ldots,S_m$ (i.e., $A=\{S_1,\ldots,S_m\}$) such that $|S_1 \cup \ldots \cup S_m| =n$. In other words, $S_1,\ldots,S_m$ covers a ground set of $n$ elements.

Is there a constant $0<c<1$ such that for arbitrary $A=\{S_1,\ldots,S_m\}$, one can always find $B \subseteq A$ such that the number of elements that belong to exactly one set in $B$ is at least $c n$?

Conjecture: for $c=1/100$, we can always find a $B \subseteq A$ such that the number of elements that belong to exactly one set in $B$ is at least $n/100$.

1

There are 1 best solutions below

1
On BEST ANSWER

Great question!

For general $n$ and $m$, No. The answer isn't simple so this is only a sketch.

We of course can visualize this as a bipartite graph; one side are the vertices $Y=\{y_1,\ldots, y_m\}$ each $y_i$ representing the set $S_i$, and on the other side are the elements $X=\{x_1,\ldots, x_n\}$ and there is an edge $y_ix_j$ iff $j \in S_i$. And the question becomes whether there is a subset $U \subseteq Y=\{y_1,\ldots, y_m\}$ s.t. there are $\theta(n)$ vertices $x_j$ adjacent to exactly one vertex in $U$.

To see this, let us construct the following graph (sketch):

$Y$ has $m\approx \frac{n}{\log n}$ vertices roughly [pick $m$ so that $m \log m = n$ working base 2], and $X = X^1 \cup X^2 \cup X^{\log m}$ where the $X^l$s are disjoint and each have cardinality $m$ as well.

For each $l$, put a random bipartite graph $Z_l$ of degree $2^{l-1}$ between $Y$ and $X^l$, and let $Z$ be the union of the $Z_l$s. Then on the one hand, for any set $U$, the number of vertices in $X$ adjacent to exactly one vertex in $U$ is the sum, over $l$, of the number of vertices in $X^l$ adjacent in $Z_l$ to exactly one vertex in $U$. But on the other hand, for any subset $U$ of $Y$, there no more than $|U|2^{l-1}$ vertices $x_j$ in $X^l$ adjacent in $Z^l$ to exactly one vertex in $U$, and if $|U|2^{l-1}$ is greater than $m$, there there no more than $\frac{8m^2}{|U|2^{l-1}}$ vertices $x_j$ in $X^l$ adjacent in $Z^l$ to exactly one vertex in $U$ [check via the probabilistic method]. Thus the maximum number of vertices in $Z$ adjacent to exactly one vertex in $U$ is no more than $\sum_l \min \left\{|U|2^{l-1}, \frac{8m^2}{|U|2^{l-1}}\right \}$. which for any possible value of $|U|$ is no more thaqn $m = o(n)$.