A note on random greedy coloring of uniform hypergraphs
A note on random greedy coloring of uniform hypergraphs
复制标题
关于均匀超图随机贪婪着色的注记
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Kozik
中科院分区：
文献类型：
--
作者：
D. Cherkashin;J. Kozik
形成不可 r 可着色的 n 均匀超图的最小边数用 m(n,r) 表示。 Erdős 和 Lovász 推测 m(n,2)=θ(n2n) 。最著名的下界 m(n,2)=Ω(n/ln(n)2n) 是由 Radhakrishnan 和 Srinivasan 在 2000 年获得的。我们对他们的结果给出了一个简单的证明。该证明基于 Pluhár 在 2009 年研究的随机贪婪着色算法的分析。该证明方法扩展到 r 着色的情况，并且我们表明，对于任何固定的 r，我们有 m(n,r)=Ω((n/ln(n))(r−1)/r rn) 改进了 2004 年的 Kostochka 的界限。我们还推导了 n 均匀超图的最小边缘度的类似界限，即不可 r 着色。 © 2014 Wiley periodicals, Inc. 随机结构。阿尔格., 47, 407–413, 2015
The smallest number of edges forming an n‐uniform hypergraph which is not r‐colorable is denoted by m(n,r). Erdős and Lovász conjectured that m(n,2)=Θ(n2n) . The best known lower bound m(n,2)=Ω(n/ln(n)2n) was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on the analysis of a random greedy coloring algorithm investigated by Pluhár in 2009. The proof method extends to the case of r‐coloring, and we show that for any fixed r we have m(n,r)=Ω((n/ln(n))(r−1)/r rn) improving the bound of Kostochka from 2004. We also derive analogous bounds on minimum edge degree of an n‐uniform hypergraph that is not r‐colorable. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 407–413, 2015