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$).

  • $\begingroup$ What does it mean for a million words to be disjoint? Do they need to be pairwise disjoint, or you need a more general notion than is present at the moment? $\endgroup$ Dec 1 '16 at 21:30
  • $\begingroup$ Pairwise disjoint. $\endgroup$
    – Alex
    Dec 1 '16 at 21:33
  • $\begingroup$ The only tiny bit of progress that I've made on this problem is the following: For any 1>m>0 and any sufficiently small delta>0, and any k>1, there exists an n and Bernoilli RVs X_1, X_2, ..., X_n such that: (A) With probability at least m there is exists subset A of {1, ..., n} of size k such that X_i=1 for i in A, and the X_i, i in A are independent. (B) The probability that at least one X_i=1 is at most m+delta. I still hope that the question I asked has a positive solution, but this fact means that it has to use more than that finding disjoint words are independent events. $\endgroup$
    – Alex
    Dec 3 '16 at 16:50

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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