# Coloring random subgraphs

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.

## No?

I haven't worked through the details yet, but what if is the union of and a sufficiently huge bipartite graph ? Then , and by taking huge enough, you can get as close to 2 as you like, forcing as small as you like.

EDIT: Whoo boy. Nevermind.