Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the size-Ramsey number of grid graphs
297
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The size-Ramsey number of a graph $F$ is the smallest number of edges in a graph $G$ with the Ramsey property for $F$, that is, with the property that any 2-colouring of the edges of $G$ contains a monochromatic copy of $F$. We prove that the size-Ramsey number of the grid graph on $ntimes n$ vertices is bounded from above by $n^{3+o(1)}$.
rate research
Read More
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 $.
Given graphs $G$ and $H$ and a positive integer $q$ say that $G$ is $q$-Ramsey for $H$, denoted $Grightarrow (H)_q$, if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The size-Ramsey number $hat{r}(H)$ of a graph $H$ is defined to be $hat{r}(H)=min{|E(G)|colon Grightarrow (H)_2}$. Answering a question of Conlon, we prove that, for every fixed $k$, we have $hat{r}(P_n^k)=O(n)$, where $P_n^k$ is the $k$-th power of the $n$-vertex path $P_n$ (i.e. , the graph with vertex set $V(P_n)$ and all edges ${u,v}$ such that the distance between $u$ and $v$ in $P_n$ is at most $k$). Our proof is probabilistic, but can also be made constructive.
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$.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.
Given a hypergraph $H$, the size-Ramsey number $hat{r}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring of the edges of $G$ with two colours there is a monochromatic copy of $H$. We prove that the size-Ramsey number of the $3$-uniform tight path on $n$ vertices $P^{(3)}_n$ is linear in $n$, i.e., $hat{r}_2(P^{(3)}_n) = O(n)$. This answers a question by Dudek, Fleur, Mubayi, and Rodl for $3$-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434], who proved $hat{r}_2(P^{(3)}_n) = O(n^{3/2} log^{3/2} n)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
