Let $W$ be a set of words of length $n$ on the three letters $a$, $b$ and $\ast$. Say that an element $w$ in $W$ ``matches" a word $w'$ of length $n$ on the letters $a$ and $b$ if each $\ast$ in $w$ can be replaced with an $a$ or a $b$ in such a way to give $w$'. Say that two words in $W$ are disjoint if, for all $i=1,\ldots,n$, the $i$-th letter of at least one of the two words is a $\ast$. 


(So, for example, if $n=4$ then $\ast a\ast b$ matches $babb$ but not $bbab$. The word $\ast\ast ab$ is disjoint from $a\ast\ast\ast$ but not $\ast a b\ast$ or $\ast\ast ab$.)


Suppose that, given a word $w'$ of length $n$ on the letters $a$ and $b$ chosen uniformly at random, with probability at least $1/20$ there is a set of a million disjoint words $w$ in $W$ that match $w'$. 


Is there some $\delta>0$ independent of $n$ and $W$ such that, given a word $w'$ of length $n$ on the letters $a$ and $b$ chosen uniformly at random, with probability at least $1/20+\delta$ there is at least one $w$ in $W$ that match $w'$?


My motivation for asking this question comes from various geometric settings (Erdős–Rényi random graphs, ...) where one might wish to know that finding one sub-object of interest is definitively more likely than finding a million disjoint sub-objects of interest, even when the class of sub-object of interest is so poorly understood that you can't use anything about this class to analyze the question.


If all the words in W are disjoint from each other, then there is a positive answer (and moreover you can take $1/20+\delta$ to be very close to $1$). 



Probability of finding one sub-object vs a million disjoint ones
As pointed out to me by Noga Alon, this was known as the Van den Berg - Kesten conjecture, which was solved by David Reimer:


*If p is the probability of matching at least one word in W, then the probability of matching at least two disjoint words in W is at most p^2.*


<http://journals.cambridge.org/article_S0963548399004113>


(The probability of matching a million disjoint words is at most p^{1,000,000}.)


