2
$\begingroup$

There is set $A$ with cardinality $2^n$. For every $x \in A$ there is $A_x$ - subset of $A$ with cardinality $2^m$, $x \in A_x$. $M=\{A_x|x \in A \}$. Are there $B \subset A$ with cardinality $\ge 2^n/Poly_1(n)$ and $C \subset M$ (some subsets of kind $A_x$) that any $x \in B$ is covered by $\ge 1$ and $\le Poly_2(n)$ sets from $C$? ($Poly_i(n)$ are some polynomials).

UPD: $m$ is not depend from $x$.

I can get positive answer if we know that every $x$ is covered by more then $k$ and less then $2k$ sets: then random $x$ don't belong to random set with probability $\ge 1 - 2^{m-n-1}$, so random $x$ don't belongs to $n\cdot2^{n - m + 1}$ sets with probability $\ge (1 - 2^{m-n-1})^{n\cdot2^{n-m + 1}} \approx e^{-n} < 2^{-n}$. So there are $n\cdot2^{n - m + 1}$ sets that covered every element from $A$. Random $x \in A$ is covered by $2n$ these sets and elements that cavered $> 100n$ sets are less then half of $A$. Removing the we getting that want.

$\endgroup$
11
  • $\begingroup$ Yes - select $B=\{x\}$ for some fix $x$ and $C=A_x$. I am sure you have intended to ask something else. Most probably the answer to your real question will be no. Some similar problems in a geometric setting can be found here: cs.elte.hu/~dom/cikkek/surveyfinal.pdf $\endgroup$
    – domotorp
    Jul 26, 2014 at 11:10
  • $\begingroup$ Sorry: $|B| \ge 2^n/Poly_1(n)$ $\endgroup$ Jul 26, 2014 at 11:14
  • $\begingroup$ And are the $A_x$ all different? Do you really want to require them to have $2^m$ elements? What is $m$? $\endgroup$
    – domotorp
    Jul 26, 2014 at 11:59
  • $\begingroup$ $A_x$ may be same. $m \le n$ $\endgroup$ Jul 26, 2014 at 12:00
  • $\begingroup$ Is $m$ a fix number or does it depend on $x$? $\endgroup$
    – domotorp
    Jul 26, 2014 at 13:35

1 Answer 1

5
$\begingroup$

For each $x$ let $\deg(x)=|\{y\in A : x\in A_y\}|$ be the number of sets that contain $x$. By the pigeonhole principle there is a number $r$ and a set $B$ of size at least $2^n/n$ such that $2^r\leq \deg(x)<2^{r+1}$ for all $x\in B$.

Set $p=10\cdot 2^{-r}$, and let $C$ be a random subset of $A$ such that $\Pr[x\in C]=p$ for all $x$ (and these events are independent). Let $d(x)=|\{ y\in C : x\in A_y\}|$. Whenever $x\in B$, we have $\Pr[1\leq d(x)\leq 100]$ is bounded away from $0$. Hence, the expected number of `good' elements in $B$ is large.

$\endgroup$
0

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.