Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThreshold Ramsey multiplicity for paths and even cycles
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 copies of $H$ taken over all two-edge-colorings of $K_{r(H)}$. The study of this concept was first proposed by Harary and Prins almost fifty years ago. In a companion paper, the authors have shown that there is a positive constant $c$ such that the threshold Ramsey multiplicity for a path or even cycle with $k$ vertices is at least $(ck)^k$, which is tight up to the value of $c$. Here, using different methods, we show that the same result also holds for odd cycles with $k$ vertices.
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}{16k^3+1}right)n+o(n)$. Here we show $R_k(C_n) leq (k-frac14)n +o(n)$, obtaining the first improvement to the coefficient of the linear term by an absolute constant.
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. Theory Ser. B 124 (2017),1-38], we determine the threshold for $G(n,p) overset{mathrm{rb}}{{longrightarrow}} C_ell$ for cycles $C_ell$ of any given length $ell geq 4$.
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$ vertices and let $Theta_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of $R_k(C_{2n})$ except that $R_k(C_{2n})ge (n-1)k+n+k-1$ for all $kge2$ and $nge2$. In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer $kgeq 1$, the Gallai-Ramsey number $GR_k(H)$ of a graph $H$ is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. We prove that $GR_k(Theta_{2n})=(n-1)k+n+1$ for all $kgeq 2$ and $ngeq 3$. This implies that $GR_k(C_{2n})=(n-1)k+n+1$ all $kgeq 2$ and $ngeq 3$. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices.
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 threshold $p_{vec H}=p_{vec H}(n)$ for the property $G(n,p)to vec H$ for the cases in which $vec H$ is an acyclic orientation of a complete graph or of a cycle.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
