论文标题
关于随机超图的2色
On the 2-colorability of random hypergraphs
论文作者
论文摘要
2彩的超图是从其顶点到两种颜色的映射，因此没有边缘是单色的。令$ h_k（n，m）$为随机的$ k $均匀的超图，上$ n $顶点，通过均匀，独立和更换的$ m $边缘形成。很容易证明，如果$ r \ geq r_c = 2^{k-1} \ ln 2 - （\ ln 2） /2 $，则使用高概率$ h_k（n，m = rn）$是不可2的。我们通过证明$ r \ r \ leq r_c -1 $进行补充，然后使用高概率$ h_k（n，m = rn）$是2色。
A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let $H_k(n,m)$ be a random $k$-uniform hypergraph on $n$ vertices formed by picking $m$ edges uniformly, independently and with replacement. It is easy to show that if $r \geq r_c = 2^{k-1} \ln 2 - (\ln 2) /2$, then with high probability $H_k(n,m=rn)$ is not 2-colorable. We complement this observation by proving that if $r \leq r_c - 1$ then with high probability $H_k(n,m=rn)$ is 2-colorable.
