Efficient proper 2-coloring of almost disjoint hypergraphs

József Beck, Sachin Lodha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages598-605
Number of pages8
ISBN (Electronic)089871513X
StatePublished - 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Other

Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country/TerritoryUnited States
CitySan Francisco
Period1/6/021/8/02

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Efficient proper 2-coloring of almost disjoint hypergraphs'. Together they form a unique fingerprint.

Cite this