7
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ this is much better worded $\endgroup$
    – Mike
    Aug 30, 2018 at 20:30
  • $\begingroup$ Upvote just for the careful editing. Very nice. $\endgroup$
    – The Count
    Aug 30, 2018 at 20:43
  • $\begingroup$ Why is the conjecture for $c=1/100$ and not, say, for $c=1/2$? Do you have examples showing that $c=1/2$ doesn't work? (There are easy examples showing that no $c\gt1/2$ will work.) $\endgroup$
    – bof
    Aug 31, 2018 at 6:47
  • $\begingroup$ Yes. 1/2 may work as well. $\endgroup$ Aug 31, 2018 at 13:41
  • $\begingroup$ I think a sufficiently small constant should work. The goal is to ensure there is such a constant which I don't mind not being tight. $\endgroup$ Aug 31, 2018 at 16:02

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Great answer! This seems right. I'll double-check and accept the answer shortly. $\endgroup$ Sep 2, 2018 at 17:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .