• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Tight Bounds on the Threshold for Permuted k-Colorability
【24h】

Tight Bounds on the Threshold for Permuted k-Colorability

机译：置换k可着色性的阈值上的严格界限

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

If each edge (u, v) of a graph G = (V, E) is decorated with a permutation π_(u,v) of k objects, we say that it has a permuted k-coloring if there is a coloring σ : V → {1,..., k} such that σ(v) ≠ π_(u,v)(σ(u)) for all (u, v) ∈ E. Based on arguments from statistical physics, we conjecture that the threshold d_k for permuted k-colorability in random graphs G(n,m = dn/2), where the permutations on the edges are uniformly random, is equal to the threshold for standard graph k-colorability. The additional symmetry provided by random permutations makes it easier to prove bounds on d_k. By applying the second moment method with these additional symmetries, and applying the first moment method to a random variable that depends on the number of available colors at each vertex, we bound the threshold within an additive constant. Specifically, we show that for any constant ε > 0, for sufficiently large k we have 2k ln k - ln k - 2 - ε ≤ d_k < 2k ln k - ln k - 1 + ε. In contrast, the best known bounds on dk for standard k-colorability leave an additive gap of about In fe between the upper and lower bounds.
机译：如果图G =（V，E）的每个边（u，v）用k个对象的排列π_（u，v）装饰，我们说如果存在着色σ，则它具有排列的k色： V→{1，...，k}，使得所有（u，v）∈E的σ（v）≠π_（u，v）（σ（u））。基于统计物理学的论点，我们推测随机图G（n，m = dn / 2）中置换k可着色性的阈值d_k等于标准图k可着色性的阈值，其中边缘上的排列是均匀随机的。随机置换提供的附加对称性使得更容易证明d_k的边界。通过应用具有这些附加对称性的第二矩方法，并将第一矩方法应用于取决于每个顶点上可用颜色的数量的随机变量，我们将阈值限制在加法常数内。具体来说，我们表明对于任何常数ε> 0，对于足够大的k，我们有2k ln k-ln k-2-ε≤d_k <2k ln k-ln k-1 +ε。相反，关于dk的标准k可着色性的最著名边界在上下边界之间留下了大约In fe的附加间隙。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号