Improved bounds and algorithms for hyper
β
Jaikumar Radhakrishnan; Aravind Srinivasan
π
Article
π
2000
π
John Wiley and Sons
π
English
β 259 KB
π 2 views
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