Coloring Random Non-Uniform Bipartite Hypergraphs

Abstract

Let $H_{n,(p_m{)}_{m=2,\dots ,M}}$ be a random non-uniform hypergraph of dimension $M$ on $2n$ vertices, where the vertices are split into two disjoint sets of size $n$, and colored by two distinct colors. Each non-monochromatic edge of size $m=2,\dots ,M$ is independently added with probability $p_m$. We show that if $p_2,\dots ,p_M$ are such that the expected number of edges in the hypergraph is at least $dn\ln n$, for some $d>0$ sufficiently large, then with probability $(1-o(1))$, one can find a proper 2-coloring of $H_{n,(p_m{)}_{m=2,\dots ,M}}$ in polynomial time. We present a polynomial time algorithm for hypergraph 2-coloring, and provide discussions on extension of the approach for $k$-coloring of non-uniform hypergraphs.

15 pages

References in corpus (2)

• Catching the k-NAESAT Threshold
• Partition Information and its Transmission over Boolean Multi-Access Channels