论文标题
颜色同构甚至循环和相关的拉姆西问题
Color isomorphic even cycles and a related Ramsey problem
论文作者
论文摘要
在本文中，我们首先研究了Conlon和Tyomkyn〜最近提出的一个新的极端问题（Arxiv：2002.00921）。给定图形$ h $和一个整数$ k \ geqslant 2 $，让$ f_ {k}（n，h）$是最少的颜色$ c $，因此存在完整的图形$ k_ {n} $的适当边缘色，其中$ k_ {n} $，$ c $ copl no $ k $ k $ k $ k $ tertex-jub tertex-disejoint copsies $ h $ $ h $ h $ h $使用多项式在有限字段上的代数属性，我们给出了$ k_ {n} $的明显适当的边缘色，并显示$ f_ {k {k {k {n，c_ {4}）=θ（n）$ k \ geqslant 3 $ 3 $ and $ n \ rightarrow \ rightarrow \ rightarrow \ rightarrow \ firce offty $。我们在边缘颜色中使用的方法可能具有一定的独立兴趣。我们还考虑了一个相关的广义拉姆西问题。对于给定的图，$ g $和$ h，$ r $ r（g，h，q）$是$ g $的边缘色（不一定正确）的最小数量，因此每副本的边缘$ h \ subseteq g $ gider都会获得至少$ q $的颜色。建立与Turán数量的指定二分图数的关系，我们获得了一些$ r（k_ {n，n}，k_ {s，t}，q）$的一般下限，并获得了$ q $的范围。
In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn~(arXiv: 2002.00921). Given a graph $H$ and an integer $k\geqslant 2$, let $f_{k}(n,H)$ be the smallest number of colors $c$ such that there exists a proper edge-coloring of the complete graph $K_{n}$ with $c$ colors containing no $k$ vertex-disjoint color-isomorphic copies of $H$. Using algebraic properties of polynomials over finite fields, we give an explicit proper edge-coloring of $K_{n}$ and show that $f_{k}(n, C_{4})=Θ(n)$ when $k\geqslant 3$ and $n\rightarrow\infty$. The methods we used in the edge-coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs $G$ and $H,$ let $r(G,H,q)$ be the minimum number of edge-colors (not necessarily proper) of $G$, such that the edges of every copy of $H\subseteq G$ together receive at least $q$ distinct colors. Establishing the relation to the Turán number of specified bipartite graphs, we obtain some general lower bounds for $r(K_{n,n},K_{s,t},q)$ with a broad range of $q$.
