Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Ramsey-Turan theory for tilings in graphs
69
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Combining two classical notions in extremal combinatorics, the study of Ramsey-Turan theory seeks to determine, for integers $mle n$ and $p leq q$, the number $mathsf{RT}_p(n,K_q,m)$, which is the maximum size of an $n$-vertex $K_q$-free graph in which every set of at least $m$ vertices contains a $K_p$. Two major open problems in this area from the 80s ask: (1) whether the asymptotic extremal structure for the general case exhibits certain periodic behaviour, resembling that of the special case when $p=2$; (2) constructing analogues of Bollobas-ErdH{o}s graphs with densities other than $1/2$. We refute the first conjecture by witnessing asymptotic extremal structures that are drastically different from the $p=2$ case, and address the second problem by constructing Bollobas-ErdH{o}s-type graphs using high dimensional complex spheres with all rational densities. Some matching upper bounds are also provided.
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.$
Given a class $mathcal{C}$ of graphs and a fixed graph $H$, the online Ramsey game for $H$ on $mathcal C$ is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in $mathcal C$, and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of $H$ at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of $H$ forever, and we say Painter wins the game. We initiate the study of characterizing the graphs $F$ such that for a given graph $H$, Painter wins the online Ramsey game for $H$ on $F$-free graphs. We characterize all graphs $F$ such that Painter wins the online Ramsey game for $C_3$ on the class of $F$-free graphs, except when $F$ is one particular graph. We also show that Painter wins the online Ramsey game for $C_3$ on the class of $K_4$-minor-free graphs, extending a result by Grytczuk, Ha{l}uszczak, and Kierstead.
We study Turan and Ramsey-type problems on edge-colored graphs. An edge-colored graph is called {em $varepsilon$-balanced} if each color class contains at least an $varepsilon$-proportion of its edges. Given a family $mathcal{F}$ of edge-colored graphs, the Ramsey function $R(varepsilon, mathcal{F})$ is the smallest $n$ for which any $varepsilon$-balanced $K_n$ must contain a copy of an $Finmathcal{F}$, and the Turan function $mathrm{ex}(varepsilon, n, mathcal{F})$ is the maximum number of edges in an $n$-vertex $varepsilon$-balanced graph which avoids all of $mathcal{F}$. In this paper, we consider this Turan function for several classes of edge-colored graphs, we show that the Ramsey function is linear for bounded degree graphs, and we prove a theorem that gives a relationship between the two parameters.
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
