اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGeometric constructions for Ramsey-Turan theory
88
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 se
t 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.
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 grap
hs, 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.
In this paper we study Turan and Ramsey numbers in linear triple systems, defined as $3$-uniform hypergraphs in which any two triples intersect in at most one vertex. A famous result of Ruzsa and Szemeredi is that for any fixed $c>0$ and large enou
gh $n$ the following Turan-type theorem holds. If a linear triple system on $n$ vertices has at least $cn^2$ edges then it contains a {em triangle}: three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called {em $s$-configurations}. The main tool is a generalization of the induced matching lemma from $aba$-patterns to more general ones. We slightly generalize $s$-configurations to {em extended $s$-configurations}. For these we cannot prove the corresponding Turan-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any $t$-coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail $C_{15}$ (configuration with blocks 123, 345, 561 and 147), are $t$-Ramsey for any $tgeq 1$. The most interesting one among them is the {em wicket}, $D_4$, formed by three rows and two columns of a $3times 3$ point matrix. In fact, the wicket is $1$-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket.
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}})$ $bi
gg($ 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.$
Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a,b,c,d,e,f,g$ and 3 edges ${a,b,c}, {c,d,e},$ and ${e,f,g}$. It is known that the $r$-color Ramsey number for $P$ is $R(P;r)=r+6$ for $rle 9$. The proof of this result relies on a caref
ul analysis of the Turan numbers for $P$. In this paper, we refine this analysis further and compute the fifth order Turan number for $P$, for all $n$. Using this number for $n=16$, we confirm the formula $R(P;10)=16$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
