Improved algorithms for colorings of simple hypergraphs and applications

详细信息    查看全文

• 作者：Jakub Kozik^a ; ^{Jakub.Kozik@uj.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Dmitry Shabanov^b ; ^{dm.shabanov.msu@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Colorings of hypergraphs ; Sparse hypergraphs ; Random recoloring method ; Van der Waerden number
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：116
• 期：Complete
• 页码：312-332
• 全文大小：440 K

文摘

The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any n-uniform simple (i.e. every two distinct edges share at most one vertex) hypergraph H with maximum edge degree at most is r  -colorable, where c>0$c>0$ is an absolute constant.

As an application of our proof technique we establish a new lower bound for Van der Waerden number W(n,r)$W(n,r)$, the minimum N such that in any r  -coloring of the set {1,…,N}$\{1,\dots ,N\}$ there exists a monochromatic arithmetic progression of length n. We show that

for some absolute constant c>0$c>0$.