|
Let $\cala$ be an $n$-uniform hypergraph. Assume that the maximum degree of $\cala$ is $D = D(\cala)$ (local condition), and $|\cala| = N = N(\cala)$ (global condition). By the Lov\'{a}sz Local Lemma (L.L.L.), if $D < \frac{2^n}{8n}$, then $\cala$ has a {\em proper} $2$-coloring ({\em i.e.} there is no monochromatic edge) {\em independently} of the value of $N$ ($N$ can be infinite). Unfortunately L.L.L. is a pure existence argument which does not give any clue of how to {\em find} a proper $2$-coloring. A hypergraph with the property that any two edges have at most one point in common is called {\em almost disjoint} ({\em e.g.} a family of lines). Assume that $\cala$ is an $n$-uniform almost disjoint hypergraph. In this special case, we provide a polynomial time (in terms of $N$) algorithm to find a proper $2$-coloring under the slightly weaker condition that $D < (2 - \delta)^n$ and $N$ is less than a doubly exponential function of $n$.
|