# Coloring random subgraphs

 Importance: Medium ✭✭
 Author(s): Bukh, Boris
 Subject: Graph Theory » Probabilistic Graph Theory
 Keywords: coloring random graph
 Posted by: mdevos on: June 18th, 2008

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.