Colorings of Random Graphs and Hypergraphs

In this paper, 2-chromatic number of a random k-uniform hypergraph H(n, k, p) in binomial model is studied. More specifically, we are trying to find probability thresholds for 2-proper r-colorability of H(n, k, p). Recall that a vertex coloring of a hypergraph is called 2-proper if each edge contains at most 2 vertices of the same color. It is known that the probability threshold corresponds to the sparse case $p=cn/\tbinom{n}{k}$, in which the expected amount of edges is a linear function of n. Denote $\hat{c}_2(n,k,r)$ - the value of c, corresponding to the threshold probability of 2-proper r-colorability of H(n,k,p). In this paper, we prove an upper bound on $\hat{c}_2(n,k,r)$ in the general case using the first moment method. Also, for k=4 we prove a lower bound on $\hat{c}_2(n, 4,r)$ using the second moment method. By that, we establish the value of $\hat{c}_2(n, 4,r)$ up to a bounded additive constant. Note, that, generally speaking, $\hat{c}_2(n, k,r)$ depends on n, but both of our bounds do not depend on n and can be considered as bounds on the constant c.