The size Ramsey number

Let denote the class of all graphsG which satisfyG(G ₁,G ₂). As a way of measuring minimality for members of, we define thesize Ramsey number (G ₁,G ₂) by.We then investigate various questions concerned with the asymptotic behaviour of.     

The Ramsey number of paths with respect to wheels

For graphs G and H, the Ramsey numberR(G,H) is the smallest positive integer n such that every graph F of order n contains G or the complement of F contains H. For the path P_n and the wheel W_m, it is proved that R(P_n,W_m)=2n-1 if m is even, m?4, and n?(m/2)(m-2), and R(P_n,W_m)=3n-2 if m is odd, m?5, and n?(m-1/2)(m-3).     

3-Color bipartite Ramsey number of cycles and paths

The -color bipartite Ramsey number of a bipartite graph is the least integer for which every -edge-colored complete bipartite graph contains a monochromatic copy of . The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2-color Ramsey number of paths. In this paper we determine asymptotically the 3-color bipartite Ramsey number of paths and (even) cycles.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Tripartite Ramsey numbers for paths

In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P_2n+1,P_2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K_3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007     

Remarks on the size Ramsey number of graphs

In this paper we prove that the cyclomatic number of a graph whose every 2-edgecolouring contains a monochromatic path witht edges is not less than 3t/4 ? 2. This fact leads to a simple non-probabilistic proof of the following theorem of Beck: $$\begin{array}{*{20}c} {lim inf{{\hat r\left( {P_t } \right)} \mathord{\left/ {\vphantom {{\hat r\left( {P_t } \right)} t}} \right. \kern-\nulldelimiterspace} t} \geqslant {9 \mathord{\left/ {\vphantom {9 4}} \right. \kern-\nulldelimiterspace} 4},} & {t \to \infty ,} \\ \end{array}$$ where \(\hat r(P_t )\) is the size Ramsey number of a pathP _t ont edges. We also show that the size Ramsey number of a (q + 1)-edge star with a tail of length one equals 4q ? 2, i.e., it is linear on the number of edges of the graph. Finally, we calculate that the upper bound for the size Ramsey number of a (q + 2)-edge star with a tail of length two is not greater than 5q + 3.     

Connected size Ramsey number for matchings vs. small stars or cycles

The notation \(F\rightarrow (G,H)\) means that if the edges of F are colored red and blue, then the red subgraph contains a copy of G or the blue subgraph contains a copy of H. The connected size Ramsey number \(\hat{r}_c(G,H)\) of graphs G and H is the minimum size of a connected graph F satisfying \(F\rightarrow (G,H)\). For \(m \ge 2,\) the graph consisting of m independent edges is called a matching and is denoted by \(mK_2\). In 1981, Erdös and Faudree determined the size Ramsey numbers for the pair \((mK_2, K_{1,t})\). They showed that the disconnected graph \(mK_{1,t} \rightarrow (mK_2,K_{1,t})\) for \( t,m \ge 1\). In this paper, we will determine the connected size Ramsey number \(\hat{r}_c(nK_2, K_{1,3})\) for \(n\ge 2\) and \(\hat{r}_c(3K_2, C_4)\). We also derive an upper bound of the connected size Ramsey number \(\hat{r}_c(nK_2, C_4),\) for \(n\ge 4\).     

The size Ramsey number of short subdivisions of bounded degree graphs

For graphs G and F, write if any coloring of the edges of G with colors yields a monochromatic copy of the graph F. Suppose is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than edges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs.     

The ith Ramsey number for matchings

The ith Ramsey number for matchings is determined. In addition, our results lead to the calculation of the Ramsey index for matchings.     

The tripartite Ramsey number for trees

We prove that for all ε>0 there are α>0 and n₀∈? such that for all n?n₀ the following holds. For any two‐coloring of the edges of K_{n, n, n} one color contains copies of all trees T of order t?(3 ? ε)n/2 and with maximum degree Δ(T)?n^α. This confirms a conjecture of Schelp. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 264–300, 2012     

A uniform estimate for rough paths

It is well known that for two p  -rough paths, if their first ⌊p⌋$\lfloor p\rfloor$ levels of iterated integrals are close in p  -variation sense, then all levels of their iterated integrals are close. In this paper, we prove that a similar result holds for the paths provided the first ⌊p⌋$\lfloor p\rfloor$ terms are close in a ‘uniform’ sense. The estimate is explicit, dimension free, and only involves the p  -variation of two paths and the ‘uniform’ distance between the first ⌊p⌋$\lfloor p\rfloor$ terms. Applications include estimation of the difference of the signatures of two uniformly close paths (Lyons and Xu, 2011 [6]), and convergence rates for Gaussian rough paths (Riedel and Xu, 2012 [7]).     

Multicolor Ramsey numbers involving graphs with long suspended paths

Let G₁,…,G_c be graphs and let H be a connected graph. Let H_n be a graph on n points which is homeomorphic to H. It is proved that if n is large enough, the Ramsey number r(G₁,…,G_c,H_n) has the form (X?1)(n?1)+T. Here X and T are two Ramsey-type functons involving G₁,…,G_c only. The properties of these functions are studied, leading to explicit evaluations in a number of cases.     

The Ramsey number for hypergraph cycles I

Let C_n denote the 3-uniform hypergraph loose cycle, that is the hypergraph with vertices v₁,…,v_n and edges v₁v₂v₃, v₃v₄v₅, v₅v₆v₇,…,v_n-1v_nv₁. We prove that every red-blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C_n, where N is asymptotically equal to 5n/4. Moreover this result is (asymptotically) best possible.