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     

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).     

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.     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

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 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.     

On the Ramsey numbers R(3, 8) and R(3, 9)

Using methods developed by Graver and Yackel, and various computer algorithms, we show that 28 ≤ R(3, 8) ≤ 29, and R(3, 9) = 36, where R(k, l) is the classical Ramsey number for 2-coloring the edges of a complete graph.     

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.     

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 R(3, 3, ⋖, 3) and Schur numbers

In this paper we show that for n ≥ 4, R(3, 3, ⋖, 3) < + 1. Consequently, a new bound for Schur numbers is also given. Also, for even n ≥ 6, the Schur number S_n is bounded by S_n < - n + 2. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 119–122, 1997     

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 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 .     

New lower bounds on the size of (n,r)‐arcs in PG(2,q)

An $\left(n,r\right)$‐arc in $\text{PG}\left(2,q\right)$ is a set of $n$ points such that each line contains at most $r$ of the selected points. It is well known that $\left(n,r\right)$‐arcs in $\text{PG}\left(2,q\right)$ correspond to projective linear codes. Let $m_r\left(2,q\right)$ denote the maximal number $n$ of points for which an $\left(n,r\right)$‐arc in $\text{PG}\left(2,q\right)$ exists. In this paper we obtain improved lower bounds on $m_r\left(2,q\right)$ by explicitly constructing $\left(n,r\right)$‐arcs. Some of the constructed $\left(n,r\right)$‐arcs correspond to linear codes meeting the Griesmer bound. All results are obtained by integer linear programming.     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.