Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe anti-Ramsey threshold of complete graphs
106
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For graphs $G$ and $H$, let $G {displaystylesmash{begin{subarray}{c} hbox{$tinyrm rb$} longrightarrow hbox{$tinyrm p$} end{subarray}}}H$ denote the property that for every proper edge-colouring of $G$ there is a rainbow $H$ in $G$. It is known that, for every graph $H$, an asymptotic upper bound for the threshold function $p^{rm rb}_H=p^{rm rb}_H(n)$ of this property for the random graph $G(n,p)$ is $n^{-1/m^{(2)}(H)}$, where $m^{(2)}(H)$ denotes the so-called maximum $2$-density of $H$. Extending a result of Nenadov, Person, v{S}koric, and Steger [J. Combin. Theory Ser. B 124 (2017),1-38] we prove a matching lower bound for $p^{rm rb}_{K_k}$ for $kgeq 5$. Furthermore, we show that $p^{rm rb}_{K_4} = n^{-7/15}$.
rate research
Read More
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$.
We call a $4$-cycle in $K_{n_{1}, n_{2}, n_{3}}$ multipartite, denoted by $C_{4}^{text{multi}}$, if it contains at least one vertex in each part of $K_{n_{1}, n_{2}, n_{3}}$. The Turan number $text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})$ $bigg($ respectively, $text{ex}(K_{n_{1},n_{2},n_{3}},{C_{3}, C_{4}^{text{multi}}})$ $bigg)$ is the maximum number of edges in a graph $Gsubseteq K_{n_{1},n_{2},n_{3}}$ such that $G$ contains no $C_{4}^{text{multi}}$ $bigg($ respectively, $G$ contains neither $C_{3}$ nor $C_{4}^{text{multi}}$ $bigg)$. We call a $C^{multi}_4$ rainbow if all four edges of it have different colors. The ant-Ramsey number $text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})$ is the maximum number of colors in an edge-colored of $K_{n_{1},n_{2},n_{3}}$ with no rainbow $C_{4}^{text{multi}}$. In this paper, we determine that $text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})=n_{1}n_{2}+2n_{3}$ and $text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})=text{ex}(K_{n_{1},n_{2},n_{3}}, {C_{3}, C_{4}^{text{multi}}})+1=n_{1}n_{2}+n_{3}+1,$ where $n_{1}ge n_{2}ge n_{3}ge 1.$
An edge-colored graph $G$ is called textit{rainbow} if every edge of $G$ receives a different color. Given any host graph $G$, the textit{anti-Ramsey} number of $t$ edge-disjoint rainbow spanning trees in $G$, denoted by $r(G,t)$, is defined as the maximum number of colors in an edge-coloring of $G$ containing no $t$ edge-disjoint rainbow spanning trees. For any vertex partition $P$, let $E(P,G)$ be the set of non-crossing edges in $G$ with respect to $P$. In this paper, we determine $r(G,t)$ for all host graphs $G$: $r(G,t)=|E(G)|$ if there exists a partition $P_0$ with $|E(G)|-|E(P_0,G)|<t(|P_0|-1)$; and $r(G,t)=max_{Pcolon |P|geq 3} {|E(P,G)|+t(|P|-2)}$ otherwise. As a corollary, we determine $r(K_{p,q},t)$ for all values of $p,q, t$, improving a result of Jia, Lu and Zhang.
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)$.
Analogues of Ramseys Theorem for infinite structures such as the rationals or the Rado graph have been known for some time. In this context, one looks for optimal bounds, called degrees, for the number of colors in an isomorphic substructure rather than one color, as that is often impossible. Such theorems for Henson graphs however remained elusive, due to lack of techniques for handling forbidden cliques. Building on the authors recent result for the triangle-free Henson graph, we prove that for each $kge 4$, the $k$-clique-free Henson graph has finite big Ramsey degrees, the appropriate analogue of Ramseys Theorem. We develop a method for coding copies of Henson graphs into a new class of trees, called strong coding trees, and prove Ramsey theorems for these trees which are applied to deduce finite big Ramsey degrees. The approach here provides a general methodology opening further study of big Ramsey degrees for ultrahomogeneous structures. The results have bearing on topological dynamics via work of Kechris, Pestov, and Todorcevic and of Zucker.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
