Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulticolor list Ramsey numbers grow exponentially
220
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 and 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.
rate research
Read More
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.
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)$.
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).
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).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
