If is a graph and , we let denote a subgraph of where each edge of appears in with independently with probability .

**Problem**Does there exist a constant so that ?

It is a classical result that the above problem has a positive answer when is the complete graph. More generally, the lower bound is known.

It is easy to obtain the bound , since we may imagine forming two random subgraphs of by putting each edge of in either or independently with probability . Then and this gives the desired bound. A similar argument with three subgraphs shows that , however these arguments all seem to require integer multiples, so the best known lower bound on of this form is .

## Bibliography

* indicates original appearance(s) of problem.