اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRestricted online Ramsey numbers of matchings and trees
223
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Consider a two-player game between players Builder and Painter. Painter begins the game by picking a coloring of the edges of $K_n$, which is hidden from Builder. In each round, Builder points to an edge and Painter reveals its color. Builders goal is to locate a particular monochromatic structure in Painters coloring by revealing the color of as few edges as possible. The fewest number of turns required for Builder to win this game is known as the restricted online Ramsey number. In this paper, we consider the situation where this particular monochromatic structure is a large matching or a large tree. We show that in any $t$-coloring of $E(K_n)$, Builder can locate a monochromatic matching on at least ${n-t+1over t+1}$ edges by revealing at most $O(nlog t)$ edges. We show also that in any $3$-coloring of $E(K_n)$, Builder can locate a monochromatic tree on at least $n/2$ vertices by revealing at most $5n$ edges.
قيم البحث
اقرأ أيضاً
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.
For ordered graphs $G$ and $H$, the ordered Ramsey number $r_<(G,H)$ is the smallest $n$ such that every red/blue edge coloring of the complete graph on vertices ${1,dots,n}$ contains either a blue copy of $G$ or a red copy of $H$, where the embeddin
g must preserve the relative order of vertices. One number of interest, first studied by Conlon, Fox, Lee, and Sudakov, is the off-diagonal ordered Ramsey number $r_<(M, K_3)$, where $M$ is an ordered matching on $n$ vertices. In particular, Conlon et al. asked what asymptotic bounds (in $n$) can be obtained for $max r_<(M, K_3)$, where the maximum is over all ordered matchings $M$ on $n$ vertices. The best-known upper bound is $O(n^2/log n)$, whereas the best-known lower bound is $Omega((n/log n)^{4/3})$, and Conlon et al. hypothesize that $r_<(M, K_3) = O(n^{2-epsilon})$ for every ordered matching $M$. We resolve two special cases of this conjecture. We show that the off-diagonal ordered Ramsey numbers for matchings in which edges do not cross are nearly linear. We also prove a truly sub-quadratic upper bound for random matchings with interval chromatic number $2$.
A path-matching of order $p$ is a vertex disjoint union of nontrivial paths spanning $p$ vertices. Burr and Roberts, and Faudree and Schelp determined the 2-color Ramsey number of path-matchings. In this paper we study the multicolor Ramsey number of
path-matchings. Given positive integers $r, p_1, dots, p_r$, define $R^{PM}(p_1, dots, p_r)$ to be the smallest integer $n$ such that in any $r$-coloring of the edges of $K_n$ there exists a path-matching of color $i$ and order at least $p_i$ for some $iin [r]$. Our main result is that for $rgeq 2$ and $p_1geq dotsgeq p_rgeq 2$, if $p_1geq 2r-2$, then [R^{PM}(p_1, dots, p_r)= p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil.] Perhaps surprisingly, we show that when $p_1<2r-2$, it is possible that $R^{PM}(p_1, dots, p_r)$ is larger than $p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil$, but in any case we determine the correct value to within a constant (depending on $r$); i.e. [p_1- (r-1) + sum_{i=2}^{r}leftlceilfrac{p_i}{3}rightrceil leq R^{PM}(p_1, dots, p_r)leq leftlceil p_1-frac{r}{3}+sum_{i=2}^rfrac{p_i}{3}rightrceil.] As a corollary we get that in every $r$-coloring of $K_n$ there is a monochromatic path-matching of order at least $3leftlfloorfrac{n}{r+2}rightrfloor$, which is essentially best possible. We also determine $R^{PM}(p_1, dots, p_r)$ in all cases when the number of colors is at most 4. The proof of the main result uses a minimax theorem for path-matchings derived from a result of Las Vergnas (extending Tuttes 1-factor theorem) to show that the value of $R^{PM}(p_1, dots, p_r)$ depends on the block sizes in covering designs (which can be also formulated in terms of monochromatic 1-cores in colored complete graphs). Then we obtain the result above by giving estimates on the block sizes in covering designs in the arbitrary (non-uniform) case.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
