CSC 2427 Assignment #1 Answers

Behdad Esfahbod Student # 993505827

1. If there is no giant component, then a.s. there is no d-cycle. So q ≥ \frac{1}{n}. And if there is a giant component, there are lots of cycles: p = (1 + ϵ)q = \frac{1+ϵ}{n}

E[C] = E[#cycles] = ∑_{i=3}^{n} \frac{1}{i}i!\binom{n}{i}p^{i} ≃ ∑_{i=3}^{n} \frac{1}{i}(\frac{i}{e})^{i}\sqrt{2πi}(\frac{en}{i})^{i}(\frac{1 + ϵ}{n})^{i} = ∑_{i=3}^{n} \sqrt{\frac{2π}{i}} (1 + ϵ)^{i}

Which when ϵ is a positive constant, tends to infinity, so there is an n after which there are at least dn cycles, which in turn means there exists a vertex that is in at least d cycles. It remains to show the concentration.

2. The way I show this is pretty much like the way we did in class for regular graphs. Consider a vertex coloring of the hyptergraph. All vertices of a certain color form an independent set. So if A is the size of the largest independent set of the graph, then χ ≥ \frac{n}{A}. Now we count the expected number of independent sets of size A:

E[X] = E[# ind. sets of sizeA] = \binom{n}{A}2^{\binom{−A}{3}} ≃ (\frac{en}{A})^{A} 2^{−A^{3}/6} ≃ (\frac{en}{A.2^{A^{2}/6}} )^{A}

The value of X would become Θ(1) around A = \sqrt{6 lg n}. For A = (1 − ϵ)\sqrt{6 ln n}, the value of X becomes n^{Aϵ} that would eventually become far greater than n^{2}.

But we cannot show concentration for X using Azuma inequality. For this, lets consider the expected number of independent sets of size A that no two share three vertices. We can estimate this value called Y by subtracting from X the number of two independent sets of size A that do share three vertices (Z):

E[Z] = E[# pairs of ind. sets of sizeAthat share three vertices]
≤ \binom{n}{A}\binom{A}{3}\binom{n − A}{A − 3}(\frac{1}{2})^{\binom{A}{3}+\binom{A}{3}−1}
≤ E(X).\frac{A^{3}}{6} (\frac{en}{A})^{A−2} (\frac{1}{2})^{A(A−1)(A−2)/6}
≃ E(X).\frac{A^{3}}{6} (\frac{en}{A.2^{A^{3}/6}} )^{A−2}

The part after E(X) is o(1) and so would become less than \frac{1}{2} soon. Then as Y ≥ X −Z we get E(Y) ≥ E(X) − E(Z):

E(Y) ≥ \frac{E(X)}{2}.

Now we can show concentration for E(Y) using Azuma’s inequality:

Pr(|Y − E(Y)| ≥ t) < 2e^{−t^{2}/2n}

By now we have shown that for f(n) = \frac{n}{\sqrt{6 lg n}}, the chromatic number of the random

hypergraph is greater than f(n)(1+o(1)). Now we try to achieve this bound by coloring the hypergraph. We color one color at a time. At each step, we take an independent set of size A and color all vertices in it with a single color. At each step there is a small probability of failure δ. We keep doing this until the set of remaining vertices is as small as \frac{n}{lg n}. Then we color each remainig vertex with its own color. Since the probability δ of failure in each step is bounded by Pr(|Y −E(Y)| ≥ E(Y)) < 2e^{−E(Y)^{2}/2n} < e^{−n}, then repeating this for less than n times, still gives us a fairly small probability of failure (< ne^{−n}). The expected number of total colors would be bounded by \frac{n}{\sqrt{6 lg n}}(1 + o(1)).