Greedy colorings of uniform hypergraphs
Greedy colorings of uniform hypergraphs
复制标题
均匀超图的贪婪着色
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
András Pluhár
中科院分区：
文献类型：
--
作者：
András Pluhár
我们给出了 Erdős 猜想的一个非常简短的证明，即不可 2 可着色的 n 均匀超图的边数至少为 f(n)2n，其中 f(n) 趋于无穷大。最初该问题由 József Beck 在 1977 年解决，表明 f(n) 至少堵塞 n。他后来通过巧妙的重新着色想法证明了 f(n) ≥ cn1/3+o(1)。这里我们证明了 f(n) 的一个弱界，即 f(n) ≥ cn1/4。我们不是重新随机着色，而是以随机顺序获取地面集并使用贪婪算法进行着色。同样的技术也适用于获取 k 着色性的界限。也可以将这个想法与 Lovász 局部引理结合起来，重新证明稀疏超图的一些已知结果（例如，如果 n ≥ 8，则 n 均匀、n 正则超图是 2 可着色的）。 © 2009 Wiley periodicals, Inc. 随机结构。阿尔格，2009
We give a very short proof of an Erdős conjecture that the number of edges in a non‐2‐colorable n‐uniform hypergraph is at least f(n)2n, where f(n) goes to infinity. Originally it was solved by József Beck in 1977, showing that f(n) at least clog n. With an ingenious recoloring idea he later proved that f(n) ≥ cn1/3+o(1). Here we prove a weaker bound on f(n), namely f(n) ≥ cn1/4. Instead of recoloring a random coloring, we take the ground set in random order and use a greedy algorithm to color. The same technique works for getting bounds on k‐colorability. It is also possible to combine this idea with the Lovász Local Lemma, reproving some known results for sparse hypergraphs (e.g., the n‐uniform, n‐regular hypergraphs are 2‐colorable if n ≥ 8). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009