Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Ramsey Theory of Henson graphs
114
0
0.0
(
0
)
Authors
Natasha Dobrinen
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Building on previous work of the author, for each finite triangle-free graph $mathbf{G}$, we determine the equivalence relation on the copies of $mathbf{G}$ inside the universal homogeneous triangle-free graph, $mathcal{H}_3$, with the smallest number of equivalence classes so that each one of the classes persists in every isomorphic subcopy of $mathcal{H}_3$. This characterizes the exact big Ramsey degrees of $mathcal{H}_3$. It follows that the triangle-free Henson graph is a big Ramsey structure.
For a $k$-vertex graph $F$ and an $n$-vertex graph $G$, an $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$. For $rin mathbb{N}$, the $r$-independence number of $G$, denoted $alpha_r(G)$ is the largest size of a $K_r$-free set of vertices in $G$. In this paper, we discuss Ramsey--Turan-type theorems for tilings where one is interested in minimum degree and independence number conditions (and the interaction between the two) that guarantee the existence of optimal $F$-tilings. For cliques, we show that for any $kgeq 3$ and $eta>0$, any graph $G$ on $n$ vertices with $delta(G)geq eta n$ and $alpha_k(G)=o(n)$ has a $K_k$-tiling covering all but $lfloortfrac{1}{eta}rfloor(k-1)$ vertices. All conditions in this result are tight; the number of vertices left uncovered can not be improved and for $eta<tfrac{1}{k}$, a condition of $alpha_{k-1}(G)=o(n)$ would not suffice. When $eta>tfrac{1}{k}$, we then show that $alpha_{k-1}(G)=o(n)$ does suffice, but not $alpha_{k-2}(G)=o(n)$. These results unify and generalise previous results of Balogh-Molla-Sharifzadeh, Nenadov-Pehova and Balogh-McDowell-Molla-Mycroft on the subject. We further explore the picture when $F$ is a tree or a cycle and discuss the effect of replacing the independence number condition with $alpha^*(G)=o(n)$ (meaning that any pair of disjoint linear sized sets induce an edge between them) where one can force perfect $F$-tilings covering all the vertices. Finally we discuss the consequences of these results in the randomly perturbed setting.
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)$.
In 1964, ErdH{o}s, Hajnal and Moon introduced a saturation version of Turans classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the ErdH{o}s-Szekeres theorem about monotone subsequences and saturati
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}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
