Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulticoloured Ramsey numbers of the path of length four
114
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $P_t$ denote the path on $t$ vertices. The $r$-coloured Ramsey number of $P_t$, denoted by $R_r(P_t)$, is the minimum integer $n$ such that whenever the complete graph on $n$ vertices is given an $r$-edge-colouring, there exists a monochromatic copy of $P_t$. In this note, we determine $R_r(P_5)$, which is approximately $3r$.
rate research
Read More
A path-matching of order $p$ is a vertex disjoint union of nontrivial paths spanning $p$ vertices. Burr and Roberts, and Faudree and Schelp determined the 2-color Ramsey number of path-matchings. In this paper we study the multicolor Ramsey number of path-matchings. Given positive integers $r, p_1, dots, p_r$, define $R^{PM}(p_1, dots, p_r)$ to be the smallest integer $n$ such that in any $r$-coloring of the edges of $K_n$ there exists a path-matching of color $i$ and order at least $p_i$ for some $iin [r]$. Our main result is that for $rgeq 2$ and $p_1geq dotsgeq p_rgeq 2$, if $p_1geq 2r-2$, then [R^{PM}(p_1, dots, p_r)= p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil.] Perhaps surprisingly, we show that when $p_1<2r-2$, it is possible that $R^{PM}(p_1, dots, p_r)$ is larger than $p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil$, but in any case we determine the correct value to within a constant (depending on $r$); i.e. [p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil leq R^{PM}(p_1, dots, p_r)leq leftlceil p_1-frac{r}{3}+sum_{i=2}^rfrac{p_i}{3}rightrceil.] As a corollary we get that in every $r$-coloring of $K_n$ there is a monochromatic path-matching of order at least $3leftlfloorfrac{n}{r+2}rightrfloor$, which is essentially best possible. We also determine $R^{PM}(p_1, dots, p_r)$ in all cases when the number of colors is at most 4. The proof of the main result uses a minimax theorem for path-matchings derived from a result of Las Vergnas (extending Tuttes 1-factor theorem) to show that the value of $R^{PM}(p_1, dots, p_r)$ depends on the block sizes in covering designs (which can be also formulated in terms of monochromatic 1-cores in colored complete graphs). Then we obtain the result above by giving estimates on the block sizes in covering designs in the arbitrary (non-uniform) case.
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).
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.
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)$.
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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
