论文标题
各种图的本地彩虹色
Local rainbow colorings for various graphs
论文作者
论文摘要
由威格森（Wigderson），阿隆（Alon）和本·埃利泽（Ben-Eliezer）提出的理论计算机科学问题的动机，从十年前系统地研究了以下极端问题。给定图表$ h $，让$ c（n，h）$是最低数字$ k $，以便以下内容。 $ e（k_ {n}）$的$ n $颜色带有$ k $颜色，每种都与$ k_ {n} $的顶点之一相关联，使得每个副本中的$ t $ t $ $ h $ in $ k_ {n} $，至少与$ v（t）$相关的一种颜色，与$ v（t）分配了$ e（t）$ e Edges $ e（T）$ e（T）$ e（T）。在本文中，我们在此问题中获得了几个新结果，包括：\ begin {inatizize} \对于短长度的路径，我们表明$ c（n，p_ {4}）=ω（n^{1/5}）$和$ c（n，p_ {t}）=ω（n^{1/3}）$带有$ t \ in \ in \ in \ {5,6 \} $ $（\ log {n}）^{ω（1）} $。 \项目我们在Alon和Ben-Eliezer的问题上取得了进展，更确切地说，我们表明$ c（n，k_ {r}）=ω（n^{2/3}）$当$ r \ geqslant 8 $。这提供了图的第一个实例，其下限超出了自然屏障$ω（n^{1/2}）$。此外，我们证明$ c（n，k_ {s，t}）=ω（n^{2/3}）$ for $ t \ geqslant s \ geqslant 7 $。 \ item当$ h $是一颗恒星时，至少$ 4 $叶子，大小至少$ 4 $的匹配或至少$ 7 $的长度路径，我们给出了$ c（n，h）$的新下限。我们还表明，对于任何图形$ h $，至少$ 6 $边缘，$ c（n，h）$在$ n $中为多项式。所有这些都改善了Alon和Ben-Eliezer获得的相应结果。
Motivated by a problem in theoretical computer science suggested by Wigderson, Alon and Ben-Eliezer studied the following extremal problem systematically one decade ago. Given a graph $H$, let $C(n,H)$ be the minimum number $k$ such that the following holds. There are $n$ colorings of $E(K_{n})$ with $k$ colors, each associated with one of the vertices of $K_{n}$, such that for every copy $T$ of $H$ in $K_{n}$, at least one of the colorings that are associated with $V(T)$ assigns distinct colors to all the edges of $E(T)$. In this paper, we obtain several new results in this problem including: \begin{itemize} \item For paths of short length, we show that $C(n,P_{4})=Ω(n^{1/5})$ and $C(n,P_{t})=Ω(n^{1/3})$ with $t\in\{5,6\}$, which significantly improve the previously known lower bounds $(\log{n})^{Ω(1)}$. \item We make progress on the problem of Alon and Ben-Eliezer about complete graphs, more precisely, we show that $C(n,K_{r})=Ω(n^{2/3})$ when $r\geqslant 8$. This provides the first instance of graph for which the lower bound goes beyond the natural barrier $Ω(n^{1/2})$. Moreover, we prove that $C(n,K_{s,t})=Ω(n^{2/3})$ for $t\geqslant s\geqslant 7$. \item When $H$ is a star with at least $4$ leaves, a matching of size at least $4$, or a path of length at least $7$, we give the new lower bound for $C(n,H)$. We also show that for any graph $H$ with at least $6$ edges, $C(n,H)$ is polynomial in $n$. All of these improve the corresponding results obtained by Alon and Ben-Eliezer.
