اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLarge book--cycle Ramsey numbers
103
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $B_n^{(k)}$ be the book graph which consists of $n$ copies of $K_{k+1}$ all sharing a common $K_k$, and let $C_m$ be a cycle of length $m$. In this paper, we first determine the exact value of $r(B_n^{(2)}, C_m)$ for $frac{8}{9}n+112le mle lceilfrac{3n}{2}rceil+1$ and $n geq 1000$. This answers a question of Faudree, Rousseau and Sheehan (Cycle--book Ramsey numbers, {it Ars Combin.,} {bf 31} (1991), 239--248) in a stronger form when $m$ and $n$ are large. Building upon this exact result, we are able to determine the asymptotic value of $r(B_n^{(k)}, C_n)$ for each $k geq 3$. Namely, we prove that for each $k geq 3$, $r(B_n^{(k)}, C_n)= (k+1+o_k(1))n.$ This extends a result due to Rousseau and Sheehan (A class of Ramsey problems involving trees, {it J.~London Math.~Soc.,} {bf 18} (1978), 392--396).
قيم البحث
اقرأ أيضاً
In this paper, we consider a variant of Ramsey numbers which we call complementary Ramsey numbers $bar{R}(m,t,s)$. We first establish their connections to pairs of Ramsey $(s,t)$-graphs. Using the classification of Ramsey $(s,t)$-graphs for small $s,
t$, we determine the complementary Ramsey numbers $bar{R}(m,t,s)$ for $(s,t)=(4,4)$ and $(3,6)$.
We prove that the number of integers in the interval [0,x] that are non-trivial Ramsey numbers r(k,n) (3 <= k <= n) has order of magnitude (x ln x)**(1/2).
Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method was developed to find asymptotic results for very large graphs, so it seems that the method is not suitable for finding small Ramsey nu
mbers. But this intuition is wrong, and we will develop a technique to do just that in this paper. We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove the exact values $R(K_4^-,K_4^-,K_4^-)=28$, $R(K_8,C_5)= 29$, $R(K_9,C_6)= 41$, $R(Q_3,Q_3)=13$, $R(K_{3,5},K_{1,6})=17$, $R(C_3, C_5, C_5)= 17$, and $R(K_4^-,K_5^-;3)= 12$. We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.
Burr and ErdH{o}s in 1975 conjectured, and Chvatal, Rodl, Szemeredi and Trotter later proved, that the Ramsey number of any bounded degree graph is linear in the number of vertices. In this paper, we disprove the natural directed analogue of the Burr
--ErdH{o}s conjecture, answering a question of Bucic, Letzter, and Sudakov. If $H$ is an acyclic digraph, the oriented Ramsey number of $H$, denoted $overrightarrow{r_{1}}(H)$, is the least $N$ such that every tournament on $N$ vertices contains a copy of $H$. We show that for any $Delta geq 2$ and any sufficiently large $n$, there exists an acyclic digraph $H$ with $n$ vertices and maximum degree $Delta$ such that [ overrightarrow{r_{1}}(H)ge n^{Omega(Delta^{2/3}/ log^{5/3} Delta)}. ] This proves that $overrightarrow{r_{1}}(H)$ is not always linear in the number of vertices for bounded-degree $H$. On the other hand, we show that $overrightarrow{r_{1}}(H)$ is nearly linear in the number of vertices for typical bounded-degree acyclic digraphs $H$, and obtain linear or nearly linear bounds for several natural families of bounded-degree acyclic digraphs. For multiple colors, we prove a quasipolynomial upper bound $overrightarrow{r_{k}}(H)=2^{(log n)^{O_{k}(1)}}$ for all bounded-degree acyclic digraphs $H$ on $n$ vertices, where $overrightarrow{r_k}(H)$ is the least $N$ such that every $k$-edge-colored tournament on $N$ vertices contains a monochromatic copy of $H$. For $kgeq 2$ and $ngeq 4$, we exhibit an acyclic digraph $H$ with $n$ vertices and maximum degree $3$ such that $overrightarrow{r_{k}}(H)ge n^{Omega(log n/loglog n)}$, showing that these Ramsey numbers can grow faster than any polynomial in the number of vertices.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
