اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRamsey numbers of path-matchings, covering designs and 1-cores
136
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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.
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 i
s 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.
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$.
Let $P_t$ denote the path on $t$ vertices. The $r$-coloured Ramsey number of $P_t$, denoted by $R_r(P_t)$, is the minimum integer $n$ such that whenever the complete graph on $n$ vertices is given an $r$-edge-colouring, there exists a monochromatic c
opy of $P_t$. In this note, we determine $R_r(P_5)$, which is approximately $3r$.
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)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
