Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 11:10
    
Sorry: $|B| \ge 2^n/Poly_1(n)$ –  Alexey Jul 26 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 at 11:59
    
$A_x$ may be same. $m \le n$ –  Alexey Jul 26 at 12:00
    
Is $m$ a fix number or does it depend on $x$? –  domotorp Jul 26 at 13:35

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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