Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe size-Ramsey number of 3-uniform tight paths
103
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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)$.
rate research
Read More
An ordered hypergraph is a hypergraph $H$ with a specified linear ordering of the vertices, and the appearance of an ordered hypergraph $G$ in $H$ must respect the specified order on $V(G)$. In on-line Ramsey theory, Builder iteratively presents edges that Painter must immediately color. The $t$-color on-line size Ramsey number $tilde R_t (G)$ of an ordered hypergraph $G$ is the minimum number of edges Builder needs to play (on a large ordered set of vertices) to force Painter using $t$ colors to produce a monochromatic copy of $G$. The monotone tight path $P_r^{(k)}$ is the ordered hypergraph with $r$ vertices whose edges are all sets of $k$ consecutive vertices. We obtain good bounds on $tilde R_t (P_r^{(k)})$. Letting $m=r-k+1$ (the number of edges in $P_r^{(k)}$), we prove $m^{t-1}/(3sqrt t)letilde R_t (P_r^{(2)})le tm^{t+1}$. For general $k$, a trivial upper bound is ${R choose k}$, where $R$ is the least number of vertices in a $k$-uniform (ordered) hypergraph whose $t$-colorings all contain $P_r^{(k)}$ (and is a tower of height $k-2$). We prove $R/(klg R)letilde R_t(P_r^{(k)})le R(lg R)^{2+epsilon}$, where $epsilon$ is any positive constant and $t(m-1)$ is sufficiently large. Our upper bounds improve prior results when $t$ grows faster than $m/log m$. We also generalize our results to $ell$-loose monotone paths, where each successive edge begins $ell$ vertices after the previous edge.
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 $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a,b,c,d,e,f,g$ and 3 edges ${a,b,c}, {c,d,e},$ and ${e,f,g}$. It is known that the $r$-color Ramsey number for $P$ is $R(P;r)=r+6$ for $rle 9$. The proof of this result relies on a careful analysis of the Turan numbers for $P$. In this paper, we refine this analysis further and compute the fifth order Turan number for $P$, for all $n$. Using this number for $n=16$, we confirm the formula $R(P;10)=16$.
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 $.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
