# Covering by subsets

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.

-
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 – domotorp Jul 26 '14 at 11:10
Sorry: $|B| \ge 2^n/Poly_1(n)$ – Alexey Jul 26 '14 at 11:14
And are the $A_x$ all different? Do you really want to require them to have $2^m$ elements? What is $m$? – domotorp Jul 26 '14 at 11:59
$A_x$ may be same. $m \le n$ – Alexey Jul 26 '14 at 12:00
Is $m$ a fix number or does it depend on $x$? – domotorp Jul 26 '14 at 13:35

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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}