اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn mixed and irredundant Ramsey numbers
185
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A set of vertices $Xsubseteq V$ in a simple graph $G(V,E)$ is irredundant if each vertex $xin X$ is either isolated in the induced subgraph $langle Xrangle$ or else has a private neighbor $yin Vsetminus X$ that is adjacent to $x$ and to no other vertex of $X$. The emph{irredundant Ramsey number} $s(m,n)$ is the smallest $N$ such that in every red-blue coloring of the edges of the complete graph of order $N$, either the blue subgraph contains an $m$-element irredundant set or the red subgraph contains an $n$-element irredundant set. The emph{mixed Ramsey number} $t(m,n)$ is the smallest $N$ for which every red-blue coloring of the edges of $K_N$ yields an $m$-element irredundant set in the blue subgraph or an $n$-element independent set in the red subgraph. In this paper, we first improve the upper bound of $t(3,n)$; using this result, we confirm that a conjecture proposed by Chen, Hattingh, and Rousseau, that is, $lim_{nrightarrow infty}frac{t(m,n)}{r(m,n)}=0$ for each fixed $mgeq 3$, is true for $mleq 4$. At last, we prove that $s(3,9)$ and $t(3,9)$ are both equal to $26$.
قيم البحث
اقرأ أيضاً
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)$.
Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method was developed to find asymptotic results for very large graphs, so it seems that the method is not suitable for finding small Ramsey nu
mbers. But this intuition is wrong, and we will develop a technique to do just that in this paper. We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove the exact values $R(K_4^-,K_4^-,K_4^-)=28$, $R(K_8,C_5)= 29$, $R(K_9,C_6)= 41$, $R(Q_3,Q_3)=13$, $R(K_{3,5},K_{1,6})=17$, $R(C_3, C_5, C_5)= 17$, and $R(K_4^-,K_5^-;3)= 12$. We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.
For $ngeq s> rgeq 1$ and $kgeq 2$, write $n rightarrow (s)_{k}^r$ if every hyperedge colouring with $k$ colours of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by textcite
{AGLM14} and textcite{EHMR84} we show that [ text{if } r geq 3 text{ and } n rightarrow (s)_k^r text{ then } 2^n rightarrow (s+1)_{k+3}^{r+1}. ] This yields an improvement for some of the known lower bounds on multicolour hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of colouring all $r$-subsets of $V$ such that no hyperedge of size $geq r+1$ is monochromatic. We provide upper and lower bounds on the number of colours necessary in terms of the chromatic number $chi(H)$. In particular we show that this number is $O(log^{(r-1)} (r chi(H)) + r)$.
Extending the concept of Ramsey numbers, Erd{H o}s and Rogers introduced the following function. For given integers $2le s<t$ let $$ f_{s,t}(n)=min {max {|W| : Wsubseteq V(G) {and} G[W] {contains no} K_s} }, $$ where the minimum is taken over all $K_
t$-free graphs $G$ of order $n$. In this paper, we show that for every $sge 3$ there exist constants $c_1=c_1(s)$ and $c_2=c_2(s)$ such that $f_{s,s+1}(n) le c_1 (log n)^{c_2} sqrt{n}$. This result is best possible up to a polylogarithmic factor. We also show for all $t-2 geq s geq 4$, there exists a constant $c_3$ such that $f_{s,t}(n) le c_3 sqrt{n}$. In doing so, we partially answer a question of ErdH{o}s by showing that $lim_{nto infty} frac{f_{s+1,s+2}(n)}{f_{s,s+2}(n)}=infty$ for any $sge 4$.
We prove that the number of integers in the interval [0,x] that are non-trivial Ramsey numbers r(k,n) (3 <= k <= n) has order of magnitude (x ln x)**(1/2).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
