Bounded colorings of multipartite graphs and hypergraphs
Bounded colorings of multipartite graphs and hypergraphs
复制标题
DOI：
10.1016/j.ejc.2017.06.023
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
Nina Kamcev;B. Sudakov;Jan Volec
中科院分区：
文献类型：
--
作者：
Nina Kamcev;B. Sudakov;Jan Volec
设c是完全n顶点图K n的边着色问题。在c中寻找适当着色和彩虹汉密尔顿环的问题是由Bollobás和Erdős在1976年提出的，并从那时起得到了广泛的研究。最近，Dudek et al.（2012）将其扩展到超图设置。我们推广了这些结果，给出了充分的局部响应。全局)对着色的限制，保证正确着色(参见。我们还研究了这些问题的多部类似问题。我们给出了完全平衡m部图的着色c包含最大度为Δ的给定图G的适当着色或彩虹副本的最优充分条件（直到一个常数因子）。我们的边界显示出增长率的惊人转变，表明问题在Δ》m和Δ《m》的体制中有着根本的不同。我们的主要工具是随机双射空间的Lu和sz<e:1>的框架，我们将其扩展到产品空间。
Let c be an edge-coloring of the complete n-vertex graph K n. The problem of finding properly colored and rainbow Hamilton cycles in c was initiated in 1976 by Bollobás and Erdős and has been extensively studied since then. Recently it was extended to the hypergraph setting by Dudek et al.(2012). We generalize these results, giving sufficient local (resp. global) restrictions on the colorings which guarantee a properly colored (resp. rainbow) copy of a given hypergraph G. We also study multipartite analogues of these questions. We give (up to a constant factor) optimal sufficient conditions for a coloring c of the complete balanced m-partite graph to contain a properly colored or rainbow copy of a given graph G with maximum degree Δ. Our bounds exhibit a surprising transition in the rate of growth, showing that the problem is fundamentally different in the regimes Δ≫ m and Δ≪ m. Our main tool is the framework of Lu and Székely for the space of random bijections, which we extend to product spaces.