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$
  • 1
    $\begingroup$ this is much better worded $\endgroup$ – Mike Aug 30 '18 at 20:30
  • $\begingroup$ Upvote just for the careful editing. Very nice. $\endgroup$ – The Count Aug 30 '18 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 '18 at 6:47
  • $\begingroup$ Yes. 1/2 may work as well. $\endgroup$ – HTV Aug 31 '18 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$ – HTV Aug 31 '18 at 16:02
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$
  • $\begingroup$ Great answer! This seems right. I'll double-check and accept the answer shortly. $\endgroup$ – HTV Sep 2 '18 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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