اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSimple proofs of estimations of Ramsey numbers and of discrepancy
133
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this expository note we present simple proofs of the lower bound of Ramsey numbers (Erdos theorem), and of the estimation of discrepancy. Neither statements nor proofs require any knowledge beyond high-school curriculum (except a minor detail). Thus they are accessible to non-specialists, in particular, to students. Our exposition is simpler than the standard exposition because no probabilistic language is used. In order to prove the existence of a `good object we prove that the number of `bad objects is smaller than the number of all objects.
قيم البحث
اقرأ أيضاً
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).
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)$.
Burr and ErdH{o}s in 1975 conjectured, and Chvatal, Rodl, Szemeredi and Trotter later proved, that the Ramsey number of any bounded degree graph is linear in the number of vertices. In this paper, we disprove the natural directed analogue of the Burr
--ErdH{o}s conjecture, answering a question of Bucic, Letzter, and Sudakov. If $H$ is an acyclic digraph, the oriented Ramsey number of $H$, denoted $overrightarrow{r_{1}}(H)$, is the least $N$ such that every tournament on $N$ vertices contains a copy of $H$. We show that for any $Delta geq 2$ and any sufficiently large $n$, there exists an acyclic digraph $H$ with $n$ vertices and maximum degree $Delta$ such that [ overrightarrow{r_{1}}(H)ge n^{Omega(Delta^{2/3}/ log^{5/3} Delta)}. ] This proves that $overrightarrow{r_{1}}(H)$ is not always linear in the number of vertices for bounded-degree $H$. On the other hand, we show that $overrightarrow{r_{1}}(H)$ is nearly linear in the number of vertices for typical bounded-degree acyclic digraphs $H$, and obtain linear or nearly linear bounds for several natural families of bounded-degree acyclic digraphs. For multiple colors, we prove a quasipolynomial upper bound $overrightarrow{r_{k}}(H)=2^{(log n)^{O_{k}(1)}}$ for all bounded-degree acyclic digraphs $H$ on $n$ vertices, where $overrightarrow{r_k}(H)$ is the least $N$ such that every $k$-edge-colored tournament on $N$ vertices contains a monochromatic copy of $H$. For $kgeq 2$ and $ngeq 4$, we exhibit an acyclic digraph $H$ with $n$ vertices and maximum degree $3$ such that $overrightarrow{r_{k}}(H)ge n^{Omega(log n/loglog n)}$, showing that these Ramsey numbers can grow faster than any polynomial in the number of vertices.
We determine the Ramsey number of a connected clique matching. That is, we show that if $G$ is a $2$-edge-coloured complete graph on $(r^2 - r - 1)n - r + 1$ vertices, then there is a monochromatic connected subgraph containing $n$ disjoint copies of
$K_r$, and that this number of vertices cannot be reduced.
A book $B_n$ is a graph which consists of $n$ triangles sharing a common edge. In this paper, we study Ramsey numbers of quadrilateral versus books. Previous results give the exact value of $r(C_4,B_n)$ for $1le nle 14$. We aim to show the exact valu
e of $r(C_4,B_n)$ for infinitely many $n$. To achieve this, we first prove that $r(C_4,B_{(m-1)^2+(t-2)})le m^2+t$ for $mge4$ and $0 leq t leq m-1$. This improves upon a result by Faudree, Rousseau and Sheehan (1978) which states that begin{align*} r(C_4,B_n)le g(g(n)), ;;text{where};;g(n)=n+lfloorsqrt{n-1}rfloor+2. end{align*} Combining the new upper bound and constructions of $C_4$-free graphs, we are able to determine the exact value of $r(C_4,B_n)$ for infinitely many $n$. As a special case, we show $r(C_4,B_{q^2-q-2}) = q^2+q-1$ for all prime power $qge4$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
