TY - GEN

T1 - Efficient proper 2-coloring of almost disjoint hypergraphs

AU - Beck, József

AU - Lodha, Sachin

PY - 2002

Y1 - 2002

N2 - Let A be an n-uniform hypergraph. Assume that the maximum degree of A is D -D(A) (local condition), and |A| = N = N(A) (global condition). By the Lovasz Local Lemma (L.L.L.), if D < 2n/8n then A has a proper 2-coloring (i.e. There is no monochromatic edge) 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 find a proper 2-coloring. A hypergraph with the property that any two edges have at most one point in common is called almost disjoint (e.g. a family of lines). Assume that A 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 -δ)n and N is less than a doubly exponential function of n.

AB - Let A be an n-uniform hypergraph. Assume that the maximum degree of A is D -D(A) (local condition), and |A| = N = N(A) (global condition). By the Lovasz Local Lemma (L.L.L.), if D < 2n/8n then A has a proper 2-coloring (i.e. There is no monochromatic edge) 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 find a proper 2-coloring. A hypergraph with the property that any two edges have at most one point in common is called almost disjoint (e.g. a family of lines). Assume that A 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 -δ)n and N is less than a doubly exponential function of n.

UR - http://www.scopus.com/inward/record.url?scp=84968866158&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84968866158&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84968866158

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 598

EP - 605

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -