ﻻ يوجد ملخص باللغة العربية
The Ramsey number $r(H)$ of a graph $H$ is the minimum integer $n$ such that any two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$. While this definition only asks for a single monochromatic copy of $H$, it is often the case that every two-edge-coloring of the complete graph on $r(H)$ vertices contains many monochromatic copies of $H$. The minimum number of such copies over all two-colorings of $K_{r(H)}$ will be referred to as the threshold Ramsey multiplicity of $H$. Addressing a problem of Harary and Prins, who were the first to systematically study this quantity, we show that there is a positive constant $c$ such that the threshold Ramsey multiplicity of a path or an even cycle on $k$ vertices is at least $(ck)^k$. This bound is tight up to the constant $c$. We prove a similar result for odd cycles in a companion paper.
The Ramsey number $r(H)$ of a graph $H$ is the minimum $n$ such that any two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$. The threshold Ramsey multiplicity $m(H)$ is then the minimum number of monochromatic
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that $(k-1)n+o(n)leq R_k(P_n)leq R_k(C_n)leq kn+o(n)$. The upper bound was recently improved by Sarkozy who showed that $R_k(C_n)leqleft(k-frac{k}{
For graphs $G$ and $H$, let $G overset{mathrm{rb}}{{longrightarrow}} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending a result of Nenadov, Person, v{S}kori{c} and Steger [J. Combin. T
For a graph $H$ and an integer $kge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $mge4$ vert
If $G$ is a graph and $vec H$ is an oriented graph, we write $Gto vec H$ to say that every orientation of the edges of $G$ contains $vec H$ as a subdigraph. We consider the case in which $G=G(n,p)$, the binomial random graph. We determine the thresho