𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improved bounds and algorithms for hypergraph 2-coloring

✍ Scribed by Jaikumar Radhakrishnan; Aravind Srinivasan

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
259 KB
Volume
16
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

We show that for all large n, every n-uniform hypergraph with at most 0 7 n/ ln n Γ— 2 n edges can be 2-colored. This makes progress on a problem of ErdΕ‘s [Nordisk Mat. Tidskrift 11, 5-10 (1963)], improving the previous-best bound of n 1/3-o 1 Γ— 2 n due to Beck [Discrete Math. 24, 127-137 (1978)]. We further generalize this to a "local" version, improving on one of the first applications of the LovΓ‘sz local lemma. We also present fast randomized algorithms that output a proper 2-coloring with high probability for n-uniform hypergraphs with at most 0 7 n/ ln n Γ— 2 n edges, for all large n. In addition, we derandomize and parallelize these algorithms, to derive NC 1 versions of these results.

πŸ“œ SIMILAR VOLUMES

Algorithms for coloring semi-random grap
Algorithms for coloring semi-random graphs
✍ C. R. Subramanian; Martin FΓΌrer; C. E. Veni Madhavan πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 373 KB πŸ‘ 2 views

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-co

Improved upper bounds for the atomic ion
Improved upper bounds for the atomic ionization potential
✍ J. C. Angulo; E. Romera πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 259 KB πŸ‘ 1 views

Two sets of rigorous upper bounds on the atomic ionization potential are derived from some known inequalities of the classical analysis. The first set of bounds are expressed in terms of radial expectation values of the electron density; they improve previously found bounds of the same kind and conv

Improved Bounds for Taylor Coefficients
Improved Bounds for Taylor Coefficients of Analytic Functions
✍ M. Neher πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons βš– 101 KB πŸ‘ 1 views

## Improved Bounds for Taylor Coefficients of Analytic Functions The practical computation of verified bounds for Taylor coefficients of analytic functions is considered. Using interval arithmetic, the bounds are constructed from Cauchy's estimate and from some of its modifications. By employing t