Probability of a subset of Bernoulli's being all 1's

Question

Suppose we have $n$ iid Bernoulli's $X_1,\ldots,X_n$ with mean $p$, and a family $\mathcal{F}$ of subsets of $[n]$. The question is how to lower bound the probability that there is a set in the family in which all of its $X_i$'s come up 1 (a "full set"), that is to show

\begin{equation} \Pr\bigg(\exists I \in \mathcal{F} : \prod_{i \in I} X_i = 1\bigg) \ge ~?. \label{eq} \end{equation}

This appears, for example, in the context of appearance of given subgraphs in random graphs, where $X_i$ is the indicator of edge $i$ in $G_{n,p}$ and $\mathcal{F}$ encodes the subgraphs of interest, see Section 5 of this paper.

When the sets in the family are small, one can get the desired lower bound, e.g., by the second moment method. But this breaks down for larger sets (concrete example below): there seems to be too much positive correlation. And all methods I have seen (e.g. Janson's inequalities) rely in one way or another on the second moment method giving non-trivial bounds.

"Concrete" question: Suppose $\mathcal{F}$ is the family of all $\sqrt{n} $-subsets and that the probability of success is $p \approx \frac{1}{\sqrt{n}}$. What is a simple/robust/right way of showing that with constant probability we get a full set? Any principles that could be useful for other families would be greatly appreciated.

(Notice that in this case getting a full set is equivalent to having at least $\sqrt{n}$ ones in our $X_i$'s, and we expect $\approx \sqrt{n}$ ones, so standard anti-concentration for the Binomial distribution quickly gives the desired bound.)

Answer 1

For the concrete question, it’s equivalent to asking for the cdf of the binomial distribution. This is well known.

In general, this is a very hard problem. Janson’s Inequality is not a second moment bound, despite the appearance of the second moment. But it generally is not too helpful in this situation. Maybe have a look at papers on random graph theory to have some idea what is known for the special case of graph properties (not a lot, in some sense). In general, there are conjectures of Kahn-Kalai and of Talagrand that try to give something like a general idea of the answer. More or less, the first moment should give the right answer up to an at most log factor; and we have some idea of when the log is not necessary.