Coloring Random Non-Uniform Bipartite Hypergraphs

Abstract: Let

H_{n, (p_{m})_{m = 2, l d o t s, M}}

be a random non-uniform hypergraph of dimension

M

on

2 n

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, l d o t s, M

is independently added with probability

p_{m}

. We show that if

p_{2}, l d o t s, p_{M}

are such that the expected number of edges in the hypergraph is at least

d n l n 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, l d o t s, 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.

This page was built for publication: Coloring Random Non-Uniform Bipartite Hypergraphs