اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMulticolour Ramsey numbers of paths and even cycles
185
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that $(k-1)n+o(n)leq R_k(P_n)leq R_k(C_n)leq kn+o(n)$. The upper bound was recently improved by Sarkozy who showed that $R_k(C_n)leqleft(k-frac{k}{16k^3+1}right)n+o(n)$. Here we show $R_k(C_n) leq (k-frac14)n +o(n)$, obtaining the first improvement to the coefficient of the linear term by an absolute constant.
قيم البحث
اقرأ أيضاً
The Ramsey number $r(H)$ of a graph $H$ is the minimum integer $n$ such that any two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$. While this definition only asks for a single monochromatic copy of $H$, it is
often the case that every two-edge-coloring of the complete graph on $r(H)$ vertices contains many monochromatic copies of $H$. The minimum number of such copies over all two-colorings of $K_{r(H)}$ will be referred to as the threshold Ramsey multiplicity of $H$. Addressing a problem of Harary and Prins, who were the first to systematically study this quantity, we show that there is a positive constant $c$ such that the threshold Ramsey multiplicity of a path or an even cycle on $k$ vertices is at least $(ck)^k$. This bound is tight up to the constant $c$. We prove a similar result for odd cycles in a companion paper.
For $ngeq s> rgeq 1$ and $kgeq 2$, write $n rightarrow (s)_{k}^r$ if every hyperedge colouring with $k$ colours of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by textcite
{AGLM14} and textcite{EHMR84} we show that [ text{if } r geq 3 text{ and } n rightarrow (s)_k^r text{ then } 2^n rightarrow (s+1)_{k+3}^{r+1}. ] This yields an improvement for some of the known lower bounds on multicolour hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of colouring all $r$-subsets of $V$ such that no hyperedge of size $geq r+1$ is monochromatic. We provide upper and lower bounds on the number of colours necessary in terms of the chromatic number $chi(H)$. In particular we show that this number is $O(log^{(r-1)} (r chi(H)) + r)$.
Given a positive integer $s$, a graph $G$ is $s$-Ramsey for a graph $H$, denoted $Grightarrow (H)_s$, if every $s$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The $s$-colour size-Ramsey number ${hat{r}}_s(H)$ of a graph $H$ is
defined to be ${hat{r}}_s(H)=min{|E(G)|colon Grightarrow (H)_s}$. We prove that, for all positive integers $k$ and $s$, we have ${hat{r}}_s(P_n^k)=O(n)$, where $P_n^k$ is the $k$th power of the $n$-vertex path $P_n$.
Given graphs $G$ and $H$ and a positive integer $k$, the emph{Gallai-Ramsey number}, denoted by $gr_{k}(G : H)$ is defined to be the minimum integer $n$ such that every coloring of $K_{n}$ using at most $k$ colors will contain either a rainbow copy o
f $G$ or a monochromatic copy of $H$. We consider this question in the cases where $G in {P_{4}, P_{5}}$. In the case where $G = P_{4}$, we completely solve the Gallai-Ramsey question by reducing to the $2$-color Ramsey numbers. In the case where $G = P_{5}$, we conjecture that the problem reduces to the $3$-color Ramsey numbers and provide several results in support of this conjecture.
For a graph $H$ and an integer $kge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $mge4$ vert
ices and let $Theta_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of $R_k(C_{2n})$ except that $R_k(C_{2n})ge (n-1)k+n+k-1$ for all $kge2$ and $nge2$. In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer $kgeq 1$, the Gallai-Ramsey number $GR_k(H)$ of a graph $H$ is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. We prove that $GR_k(Theta_{2n})=(n-1)k+n+1$ for all $kgeq 2$ and $ngeq 3$. This implies that $GR_k(C_{2n})=(n-1)k+n+1$ all $kgeq 2$ and $ngeq 3$. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
