Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRamsey Numbers of Connected Clique Matchings
90
0
0.0
(
0
)
Authors
Barnaby Roberts
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 embedding 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$.
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.
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)$.
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).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
