Multipass greedy coloring of simple uniform hypergraphs1. Issue 1 (6th October 2015)

• Record Type: Journal Article
• Authors: Kozik, Jakub
• Is Part Of: Random structures & algorithms. Volume 48:Issue 1(2016)
• Page Start: 125
• Page End: 146
• Publication Date: 2015-10-06
• Subjects: hypergraph coloring -- greedy algorithm -- van der Waerden numbers; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20613
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Let m * ( n ) be the minimum number of edges in an n ‐uniform simple hypergraph that is not two colorable. We prove that m * ( n ) = Ω ( 4 n / ln 2 ( n ) ) . Our result generalizes to r ‐coloring of b ‐simple uniform hypergraphs. For fixed r and b we prove that a maximum vertex degree in b ‐simple n ‐uniform hypergraph that is not r ‐colorable must be Ω ( r n / ln ( n ) ) . By trimming arguments it implies that every such graph has Ω ( ( r n / ln ( n ) ) b + 1 / b ) edges. For any fixed r ⩾ 2 our techniques yield also a lower bound Ω ( r n / ln ( n ) ) for van der Waerden numbers W ( n, r ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 125–146, 2016