Hypergraph Two-Coloring in the Streaming Model

We consider space-efficient algorithms for two-coloring $n$-uniform hypergraphs $H=(V,E)$ in the streaming model, when the hyperedges arrive one at a time. It is known that any such hypergraph with at most $0.7 \sqrt{\frac{n}{\ln n}} 2^n$ hyperedges has a two-coloring [Radhakrishnan & Srinivasan, RSA, 2000], which can be found deterministically in polynomial time, if allowed full access to the input. 1. Let $s^D(v, q, n)$ be the minimum space used by a deterministic one-pass streaming algorithm that on receiving an $n$-uniform hypergraph $H$ on $v$ vertices and $q$ hyperedges $(q \leq 0.7 \sqrt{\frac{n}{\ln n}} 2^n)$, produces a proper two-coloring of $H$. We show that $s^D(n^2, q, n) = \Omega(q/n)$. This shows that no efficient deterministic streaming algorithm can match the performance of the Radhakrishnan-Srinivasan algorithm. 2. Let $s^R(v, q,n)$ be the minimum space used by a randomized one-pass streaming algorithm that on receiving an $n$-uniform hypergraph $H$ on $v$ vertices and $q$ hyperedges with high probability produces a proper two-coloring of $H$ (or declares failure). We show that $s^R(v, \frac{1}{10}\sqrt{\frac{n}{\ln n}} 2^n, n) = O(v \log v)$ by giving an efficient randomized streaming algorithm. 3. We show that for any $4 \leq t \leq \frac{n^2}{2n-1}$, $s^R\left(\frac{n^2}{t}, 2^{n-2}\exp(\frac{t}{8}), n\right) = O(n^2/t)$; in particular, every $n$-uniform hypergraph with at most $\frac{n^2}{t}$ vertices and $ 2^{n-1}\exp(\frac{t}{8})$ hyperedges is two-colorable. This shows that every non-two-colorable hypergraph on $o(n^2)$ vertices has $\omega(n^22^n)$ hyperedges. The above results are inspired by the study of the number $q(n)$, the minimum possible number of hyperedges in a $n$-uniform hypergraph that is not two-colorable. It is known that $q(n) = \Omega(\sqrt{\frac{n}{\ln n}})$ [Radhakrishnan-Srinivasan] and $ q(n)= O(n^2 2^n)$ [Erdos, 1963].