An interesting bound (problem from Rudi’s Modern coding theory book) regarding the chromatic number of a random graph. I first attempted it during the course. Here is the problem statement:
C.5 (Concentration of the Chromatic Number – Spencer and Shamir). Consider a graph on vertices. The chromatic number of a graph , denoted by , is the smallest number of colors needed to color all vertices so that no two vertices which are joined by an edge have the same color. Consider the standard ensemble of random graphs on vertices with parameter : to sample from this ensemble, pick vertices and connect each of the ordered pairs of vertices independently from all other connections with probability . Show that for this ensemble
.
My solution is as folllows: (PDF typeset as single file is available here. Look for problem 3)
Let is a random graph with vertices. If is the probability that a given edge is in . The probability space be . Let be a filter on the set of all such random graphs. We can define a Martingale as follows:
where
and is the Chromatic number of . Chromatic number changes at most by one , when the information about the new edge comes in. Clearly, satisfies the conditions for Azuma’s inequality.
is a Martingale, with ). Let . Clearly
Now we can use the Azuma’s inequality on to get,
.
Since , the result
follows.
1 comment
Comments feed for this article
August 16, 2010 at 2:08 pm
cstheory
I think there might be a slight problem with the argument. It is this : The number of edges is and not . Thus even though the influence of each individual edge is only 1, the naive application of the martingale method would only give
.
Unless I am mistaken somehow. This is not very serious though. One could group edges incident at 1 vertex into 1 variable that is independent from the rest. Now we have only variables and one can argue the influence of each of them is at most 1. This would give the desired bound. But please correct me if I am wrong ..