Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRamsey simplicity of random graphs
59
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is $q$-Ramsey for another graph $H$ if in any $q$-edge-colouring of $G$ there is a monochromatic copy of $H$, and the classic Ramsey problem asks for the minimum number of vertices in such a graph. This was broadened in the seminal work of Burr, ErdH{o}s, and Lovasz to the investigation of other extremal parameters of Ramsey graphs, including the minimum degree. It is not hard to see that if $G$ is minimally $q$-Ramsey for $H$ we must have $delta(G) ge q(delta(H) - 1) + 1$, and we say that a graph $H$ is $q$-Ramsey simple if this bound can be attained. Grinshpun showed that this is typical of rather sparse graphs, proving that the random graph $G(n,p)$ is almost surely $2$-Ramsey simple when $frac{log n}{n} ll p ll n^{-2/3}$. In this paper, we explore this question further, asking for which pairs $p = p(n)$ and $q = q(n,p)$ we can expect $G(n,p)$ to be $q$-Ramsey simple. We resolve the problem for a wide range of values of $p$ and $q$; in particular, we uncover some interesting behaviour when $n^{-2/3} ll p ll n^{-1/2}$.
rate research
Read More
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.
We study graphs with the property that every edge-colouring admits a monochromatic cycle (the length of which may depend freely on the colouring) and describe those graphs that are minimal with this property. We show that every member in this class reduces recursively to one of the base graphs $K_5-e$ or $K_4vee K_4$ (two copies of $K_4$ identified at an edge), which implies that an arbitrary $n$-vertex graph with $e(G)geq 2n-1$ must contain one of those as a minor. We also describe three explicit constructions governing the reverse process. As an application we are able to establish Ramsey infiniteness for each of the three possible chromatic subclasses $chi=2, 3, 4$, the unboundedness of maximum degree within the class as well as Ramsey separability of the family of cycles of length $leq l$ from any of its proper subfamilies.
For an integer $qge 2$, a graph $G$ is called $q$-Ramsey for a graph $H$ if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. If $G$ is $q$-Ramsey for $H$, yet no proper subgraph of $G$ has this property then $G$ is called $q$-Ramsey-minimal for $H$. Generalising a statement by Burr, Nev{s}etv{r}il and Rodl from 1977 we prove that, for $qge 3$, if $G$ is a graph that is not $q$-Ramsey for some graph $H$ then $G$ is contained as an induced subgraph in an infinite number of $q$-Ramsey-minimal graphs for $H$, as long as $H$ is $3$-connected or isomorphic to the triangle. For such $H$, the following are some consequences. (1) For $2le r< q$, every $r$-Ramsey-minimal graph for $H$ is contained as an induced subgraph in an infinite number of $q$-Ramsey-minimal graphs for $H$. (2) For every $qge 3$, there are $q$-Ramsey-minimal graphs for $H$ of arbitrarily large maximum degree, genus, and chromatic number. (3) The collection ${{cal M}_q(H) : H text{ is 3-connected or } K_3}$ forms an antichain with respect to the subset relation, where ${cal M}_q(H)$ denotes the set of all graphs that are $q$-Ramsey-minimal for $H$. We also address the question which pairs of graphs satisfy ${cal M}_q(H_1)={cal M}_q(H_2)$, in which case $H_1$ and $H_2$ are called $q$-equivalent. We show that two graphs $H_1$ and $H_2$ are $q$-equivalent for even $q$ if they are $2$-equivalent, and that in general $q$-equivalence for some $qge 3$ does not necessarily imply $2$-equivalence. Finally we indicate that for connected graphs this implication may hold: Results by Nev{s}etv{r}il and Rodl and by Fox, Grinshpun, Liebenau, Person and Szabo imply that the complete graph is not $2$-equivalent to any other connected graph. We prove that this is the case for an arbitrary number of colours.
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}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
