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     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Search algorithm for Ramsey graphs by union of group orbits

An algorithm for the construction of Ramsey graphs with a given automorphism group G is presented. To find a graph on n vertices with no clique of k vertices, K_k, and no independent set of l vertices, ¯K_l, k, l ≤ n, with an automorphism group G, a Boolean formula α based on the G-orbits of k-subsets and l-subsets of vertices is constructed from incidence matrices belonging to G. This Boolean formula is satisfiable if and only if the desired graph exists, and each satisfying assignment to α specifies a set of orbits of pairs of vertices whose union gives the edges of such a graph. Finding these assignments is basically equivalent to the conversion of α from CNF to DNF (conjunctive to disjunctive normal form). Though the latter problem is NP-hard, we present an “efficient” method to do the conversion for the formulas that appear in this particular problem. When G is taken to be the dihedral group D_n for n ≤ 101, this method matches all of the previously known cyclic Ramsey graphs, as reported by F. R. K. Chung and C. M. Grinstead [“A Survey of Bounds for Classical Ramsey Numbers,” Journal of Graph Theory, 7 (1983), 25–38], in dramatically smaller computer time when compared to the time required by an exhaustive search. Five new lower bounds for the classical Ramsey numbers are established: R(4, 7) ? 47, R(4, 8) ? 52, R(4, 9) ? 69, R(5,7) ? 76, and R(5, 8) ? 94. Also, some previously known cyclic graphs are shown to be unique up to isomorphism.     

On Ramsey Numbers for Trees Versus Wheels of Five or Six Vertices

 For given two graphs G dan H, the Ramsey number R(G,H) is the smallest positive integer n such that every graph F of order n must contain G or the complement of F must contain H. In [12], the Ramsey numbers for the combination between a star S _n and a wheel W _m for m=4,5 were shown, namely, R(S _n ,W ₄)=2n−1 for odd n and n≥3, otherwise R(S _n ,W ₄)=2n+1, and R(S _n ,W ₅)=3n−2 for n≥3. In this paper, we shall study the Ramsey number R(G,W _m ) for G any tree T _n . We show that if T _n is not a star then the Ramsey number R(T _n ,W ₄)=2n−1 for n≥4 and R(T _n ,W ₅)=3n−2 for n≥3. We also list some open problems. Received: October, 2001 Final version received: July 11, 2002 RID="*" ID="*" This work was supported by the QUE Project, Department of Mathematics ITB Indonesia Acknowledgments. We would like to thank the referees for several helpful comments.     

Sum-free sets and Ramsey numbers

In this note we obtain new lower bounds for the Ramsey numbers R(5, 5) and R(5, 6). The method is based on computational results of partitioning the integers into sum-free sets. We obtain R(5, 5)?42 and R(5, 6)?53.     

On Pattern Ramsey Numbers of Graphs

A color pattern is a graph whose edges are partitioned into color classes. A family F of color patterns is a Ramsey family if there is some integer N such that every edge-coloring of K_N has a copy of some pattern in F. The smallest such N is the (pattern) Ramsey number R(F) of F. The classical Canonical Ramsey Theorem of Erdös and Rado [4] yields an easy characterization of the Ramsey families of color patterns. In this paper we determine R(F) for all families consisting of equipartitioned stars, and we prove that when F consists of a monochromatic star of size s and a polychromatic triangle.Acknowledgments. We thank the referees for pointing out several references where related results appeared.Project sponsored by the National Security Agency under Grant Number MDA904-03-1-0037. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.Final version received: January 9, 2004     

Constrained Ramsey numbers for rainbow matching

The Ramsey number R_k(G) of a graph G is the minimum number N, such that any edge coloring of K_N with k colors contains a monochromatic copy of G. The constrained Ramsey number f(G, T) of the graphs G and T is the minimum number N, such that any edge coloring of K_N with any number of colors contains a monochromatic copy of G or a rainbow copy of T. We show that these two quantities are closely related when T is a matching. Namely, for almost all graphs G, f(G, tK₂) = R_{t ? 1}(G) for t≥2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:91‐95, 2011     

On irredundant Ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the smallest p such that in every two-coloring of the edges of K_p using colors red (R) and blue (B), either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We develop techniques to obtain upper bounds for irredundant Ramsey numbers of the form s(3, n) and prove that 18 ≤ s(3,7) ≤ 19.     

Binomial Coefficients and Zero-Sum Ramsey Numbers

A counting argument is developed and divisibility properties of the binomial coefficients are combined to prove, among other results, that[formula]whereK_n, resp.K^k_n, is the complete, resp. completek-uniform, hypergaph andR(K_n, Z_p),R(K^k_n, Z₂) are the corresponding zero-sum Ramsey numbers.     

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.

     

CO‐irredundant Ramsey numbers for graphs

The study of the CO‐irredundant Ramsey numbers t(n₁, ···, n_k) is initiated. It is shown that several values and bounds for these numbers may be obtained from the well‐studied generalized graph Ramsey numbers and the values of t(4, 5), t(4, 6) and t(3, 3, m) are calculated. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 258–268, 2000     

The Largest Left Quotient Ring of a Ring

The left quotient ring (i.e., the left classical ring of fractions) Q_cl(R) of a ring R does not always exist and still, in general, there is no good understanding of the reason why this happens. In this article, existence of the largest left quotient ring Q_l(R) of an arbitrary ring R is proved, i.e., Q_l(R) = S₀(R)^?1R where S₀(R) is the largest left regular denominator set of R. It is proved that Q_l(Q_l(R)) = Q_l(R); the ring Q_l(R) is semisimple iff Q_cl(R) exists and is semisimple; moreover, if the ring Q_l(R) is left Artinian, then Q_cl(R) exists and Q_l(R) = Q_cl(R). The group of units Q_l(R)* of Q_l(R) is equal to the set {s^?1t | s, t ∈ S₀(R)} and S₀(R) = R ∩ Q_l(R)*. If there exists a finitely generated flat left R-module which is not projective, then Q_l(R) is not a semisimple ring. We extend slightly Ore's method of localization to localizable left Ore sets, give a criterion of when a left Ore set is localizable, and prove that all left and right Ore sets of an arbitrary ring are localizable (not just denominator sets as in Ore's method of localization). Applications are given for certain classes of rings (semiprime Goldie rings, Noetherian commutative rings, the algebra of polynomial integro-differential operators).     

Generalized Sets of Lengths

LetRbe a Dedekind domain and (R) the set of irreducible elements ofR. In this paper, we study the sets _R(n) = {m | α₁,…,α_n, β₁,…,β_m (R) such that α₁,…,α_n = β₁,…,β_m}, wherenis a positive integer. We show, in constrast to indications in some earlier work, that the sets _R(n) are not completely determined by the Davenport constant of the class group ofR. We offer some specific constructions for Dedekind domains with small class groups, and show how these sets are generalizations of the sets studied earlier by Geroldinger [[9], [10]].     

Elementary equivalence of generalized incidence rings

In this paper, we prove that if two generalized incidence rings I(P ₁ ,R ₁) and I(P ₂ ,R ₂) are elementarily equivalent, then the corresponding ordered sets (P ₁ ,R ₁) and (P ₂ ,R ₂) are elementarily equivalent.     

A note on Ramsey multiplicity

If G₁ and G₂ are graphs and the Ramsey number r(G₁, G₂) = p, then the fewest number of G₁ in G and G₂ in ? (G complement) that occur in a graph G on p points is called the Ramsey multiplicity and denoted R(G₁, G₂). In [2, 3] the diagonal (i.e. G₁ = G₂) Ramsey multiplicities are derived for graphs on 3 and 4 points, with the exception of K₄. In this note an upper bound is established for R(K_s, K₁). Specifically, we show that R(K₄, K₄) ? 12.     

Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr_∗(G,H) as the smallest integer k such that every 2-coloring of the edges of K_r−K_1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

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.     

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     

Coding into Ramsey sets

In [6] W. T. Gowers formulated and proved a Ramsey-type result which lies at the heart of his famous dichotomy for Banach spaces. He defines the notion of weakly Ramsey set of block sequences of an infinite dimensional Banach space and shows that every analytic set of block sequences is weakly Ramsey. We show here that Gowers’ result follows quite directly from the fact that all G_δ sets are weakly Ramsey, if the Banach space does not contain c₀, and from the fact that all F_σδ sets are weakly Ramsey, in the case of an arbitrary Banach space. We also show that every result obtained by the application of Gowers’ theorem to an analytic set can also be obtained by applying the Theorem to a F_σδ set (or to a G_δ set if the space does not contain c₀). This fact explains why the only known applications of this technique are based on very low-ranked Borel sets (open, closed, F_σ, or G_δ).     

Der Satz von Tits für PGL2(R), R ein kommutativer Ring vom stabilen Rang 2

Certain permutation groups on sets with distance relation are characterized as groups of projectivities PGL₂(R) on the projective line over a commutative ring R of stable rank 2, thus generalizing a classical result of Tits where R is a field.