MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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: – 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.

share|cite|improve this answer

Your Answer


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.