اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn improved lower bound for multicolor Ramsey numbers and the half-multiplicity Ramsey number problem
99
0
0.0
(
0
)
تأليف
Will Sawin
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The multicolor Ramsey number problem asks, for each pair of natural numbers $ell$ and $t$, for the largest $ell$-coloring of a complete graph with no monochromatic clique of size $t$. Recent works of Conlon-Ferber and Wigderson have improved the longstanding lower bound for this problem. We make a further improvement by replacing an explicit graph appearing in their constructions by a random graph. Graphs useful for this construction are exactly those relevant for a problem of ErdH{o}s on graphs with no large cliques and few large independent sets. We also make some basic observations about this problem.
قيم البحث
اقرأ أيضاً
The list Ramsey number $R_{ell}(H,k)$, recently introduced by Alon, Bucic, Kalvari, Kuperwasser, and Szabo, is a list-coloring variant of the classical Ramsey number. They showed that if $H$ is a fixed $r$-uniform hypergraph that is not $r$-partite a
nd the number of colors $k$ goes to infinity, $e^{Omega(sqrt{k})} le R_{ell} (H,k) le e^{O(k)}$. We prove that $R_{ell}(H,k) = e^{Theta(k)}$ if and only if $H$ is not $r$-partite.
Given a positive integer $ r $, the $ r $-color size-Ramsey number of a graph $ H $, denoted by $ hat{R}(H, r) $, is the smallest integer $ m $ for which there exists a graph $ G $ with $ m $ edges such that, in any edge coloring of $ G $ with $ r $
colors, $G$ contains a monochromatic copy of $ H $. Haxell, Kohayakawa and L uczak showed that the size-Ramsey number of a cycle $ C_n $ is linear in $ n $ i.e. $ hat{R}(C_n, r) leq c_rn $, for some constant $ c_r $. Their proof, however, is based on the Szemeredis regularity lemma and so no specific constant $ c_r $ is known. Javadi, Khoeini, Omidi and Pokrovskiy gave an alternative proof for this result which avoids using of the regularity lemma. Indeed, they proved that if $ n $ is even, then $ c_r $ is exponential in $ r $ and if $ n $ is odd, then $ c_r $ is doubly exponential in $ r $. oindent In this paper, we improve the bound $c_r$ and prove that $c_r$ is polynomial in $r$ when $n$ is even and is exponential in $r$ when $n$ is odd. We also prove that in the latter case, it cannot be improved to a polynomial bound in $r$. More precisely, we prove that there are some positive constants $c_1,c_2$ such that for every even integer $n$, we have $c_1r^2nleq hat{R}(C_n,r)leq c_2r^{120}(log^2 r)n$ and for every odd integer $n$, we have $c_1 2^{r}n leq hat{R}(C_n, r)leq c_22^{16 r^2+2log r}n $.
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)$.
A fan $F_n$ is a graph consisting of $n$ triangles, all having precisely one common vertex. Currently, the best known bounds for the Ramsey number $R(F_n)$ are $9n/2-5 leq R(F_n) leq 11n/2+6$, obtained by Chen, Yu and Zhao. We improve the upper bound to $31n/6+O(1)$.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
