Linear upper bounds for local Ramsey numbers

A coloring of the edges of a graph is called alocal k-coloring if every vertex is incident to edges of at mostk distinct colors. For a given graphG, thelocal Ramsey number, r _loc ^k (G), is the smallest integern such that any localk-coloring ofK _n , (the complete graph onn vertices), contains a monochromatic copy ofG. The following conjecture of Gyárfás et al. is proved here: for each positive integerk there exists a constantc = c(k) such thatr _loc ^k (G) cr ^k (G), for every connected grraphG (wherer ^k (G) is theusual Ramsey number fork colors). Possible generalizations for hypergraphs are considered.On leave from the Institute of Mathematics, Technical University of Warsaw, Poland.While on leave at University of Louisville, Fall 1985.     

Upper bounds for Ramsey numbers

The Ramsey number R(G₁,G₂,…,G_k) is the least integer p so that for any k-edge coloring of the complete graph K_p, there is a monochromatic copy of G_i of color i. In this paper, we derive upper bounds of R(G₁,G₂,…,G_k) for certain graphs G_i. In particular, these bounds show that R(9,9)6588 and R(10,10)23556 improving the previous best bounds of 6625 and 23854.     

New lower bounds of some diagonal Ramsey numbers

A new construction of self-complementary graphs containing no K₁₀ or K₁₁ is described. This construction gives the Ramsey number lower bounds r(10,10) ≧ 458 and r(11,11) ≧ 542.     

Lower bounds for lower Ramsey numbers

For any graph G, let i(G) and μ;(G) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers m and n, the lower Ramsey number s(m, n) is the largest integer p so that every graph of order p has i(G) ≤ m or μ;(G) ≤ n. In this paper we give several new lower bounds for s (m, n) as well as determine precisely the values s(1, n).     

Lower bounds for multicolor classical Ramsey numbers

A method is put forward to establish the lower bounds for somen-color classical Ramsey numbers . With this method six new explicit lower boundsR ₄(4) ≥458,R ₃(5) ≥ 242,R ₃(6)≥1070,R ₃(7) ≥ 1214,R ₃(8) ≥2834 andR ₃(9) ≥ 5282 are obtained using a computer. Project supported by Guangxi Natural Science Foundation     

Constructive lower bounds for off-diagonal Ramsey numbers

We describe an explicit construction whicy, for some fixed absolute positive constant ε, produces, for every integers>1 and all sufficiently largem, a graph on at least vertices containing neither a clique of sizes nor an independent set of sizem. Part of this work was done at the Institute for Advanced Study, Princeton, NJ 08540, USA. Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research supported in part by a grant A1019901 of the Academy of Sciences of the Czech Republic and by a cooperative research grant INT-9600919/ME-103 from the NSF (USA) and the MŠMT (Czech Republic).     

A note on Ramsey numbers for books

The book with n pages B_n is the graph consisting of n triangles sharing an edge. The book Ramsey number r(B_m,B_n) is the smallest integer r such that either B_m ? G or B_n ? G for every graph G of order r. We prove that there exists a positive constant c such that r(B_m,B_n) = 2n + 3 for all n ≥ cm. Our proof is based mainly on counting; we also use a result of Andrásfai, Erd?s, and Sós stating that triangle‐free graphs of order n and minimum degree greater than 2n/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph Theory     

New upper bound formulas with parameters for Ramsey numbers

In this paper, we obtain some new results R(5,12)?848, R(5,14)?1461, etc., and we obtain new upper bound formulas for Ramsey numbers with parameters.     

A survey of bounds for classical Ramsey numbers

This paper is a survey of the methods used for determining exact values and bounds for the classical Ramsey numbers in the case that the sets being colored are two-element sets. Results concerning the asymptotic behavior of the Ramsey functions R(k,l) and R_m(k) are also given.     

Asymptotic bounds for irredundant and mixed Ramsey numbers

The irredundant Ramsey number s(m, n) is the smallest N such that in every red-blue coloring of the edges of K_N, either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. The definition of the mixed Ramsey number t(m, n) differs from s(m, n) in that the n-element irredundant set is replaced by an n-element independent set. We prove asymptotic lower bounds for s(n, n) and t(m, n) (with m fixed and n large) and a general upper bound for t(3, n). © 1993 John Wiley & Sons, Inc.     

Some geometric structures and bounds for Ramsey numbers

We investigate several bounds for both K_2,m−K_1,n Ramsey numbers and K_2,m−K_1,n bipartite Ramsey numbers, extending some previous results. Constructions based on certain geometric structures (designs, projective planes, unitals) yield classes of near-optimal bounds or even exact values. Moreover, relationships between these numbers are also discussed.     

New upper bounds for kissing numbers from semidefinite programming

Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases .

     

On upper domination Ramsey numbers for graphs

The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, β(B)⩾m or β(R)⩾n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or Γ(R)⩾n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or β(R)⩾n. Since β(G)⩽Γ(G) for every graph G, u(m,n)⩽v(m,n)⩽r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15.     

Star-critical Ramsey numbers for large generalized fans and books

In this paper, we show that for any fixed integers $m\ge 2$ and $t\ge 2$, the star-critical Ramsey number $r_1(K_1+n{K}_t,K_{m+1})=(m?1)tn+t$ for all sufficiently large $n$. Furthermore, for any fixed integers $p\ge 2$ and $m\ge 2$, $r_1(K_p+n{K}_1,K_{m+1})=(m?1+o\left(1\right))n$ as $n\to \infty$.     

Lower bounds of Ramsey numbers based on cubic residues

A method to improve the lower bounds for Ramsey numbers R(k,l) is provided: one may construct cyclic graphs by using cubic residues modulo the primes in the form p=6m+1 to produce desired examples. In particular, we obtain 16 new lower bounds, which are

R(6,12)230, R(5,15)242, R(6,14)284, R(6,15)374,R(6,16)434, R(6,17)548, R(6,18)614, R(6,19)710,R(6,20)878, R(6,21)884, R(7,19)908, R(6,22)1070,R(8,20)1094, R(7,21)1214, R(9,20)1304, R(8,21)1328.

     

New bounds for the distance Ramsey number

In this paper we study the distance Ramsey number $R_D(s,t,d)$. The distance Ramsey number $R_D(s,t,d)$ is the minimum number $n$ such that for any graph $G$ on $n$ vertices, either $G$ contains an induced $s$-vertex subgraph isomorphic to a distance graph in ${\mathbb{R}}^d$ or $\stackrel{?}{G}$ contains an induced $t$-vertex subgraph isomorphic to the distance graph in ${\mathbb{R}}^d$. We obtain the upper and lower bounds on $R_D(s,s,d)$, which are similar to the bounds for the classical Ramsey number $R(?\frac{s}{[d/2]}?,?\frac{s}{[d/2]}?)$.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .