Conditions on Ramsey Nonequivalence

Given a graph H , a graph G is called a Ramsey graph of H if there is a monochromatic copy of H in every coloring of the edges of G with two colors. Two graphs G , H are called Ramsey equivalent if they have the same set of Ramsey graphs. Fox et al. (J Combin Theory Ser B 109 (2014), 120–133) asked whether there are two nonisomorphic connected graphs that are Ramsey equivalent. They proved that a clique is not Ramsey equivalent to any other connected graph. Results of Ne?et?il et al. showed that any two graphs with different clique number (Combinatorica 1(2) (1981), 199–202) or different odd girth (Comment Math Univ Carolin 20(3) (1979), 565–582) are not Ramsey equivalent. These are the only structural graph parameters we know that “distinguish” two graphs in the above sense. This article provides further supportive evidence for a negative answer to the question of Fox et al. by claiming that for wide classes of graphs, the chromatic number is a distinguishing parameter. In addition, it is shown here that all stars and paths and all connected graphs on at most five vertices are not Ramsey equivalent to any other connected graph. Moreover, two connected graphs are not Ramsey equivalent if they belong to a special class of trees or to classes of graphs with clique‐reduction properties.     

On an anti‐Ramsey problem of Burr,Erdős,Graham, and T. Sós

Given a graph L, in this article we investigate the anti‐Ramsey number χ_S(n,e,L), defined to be the minimum number of colors needed to edge‐color some graph G(n,e) with n vertices and e edges so that in every copy of L in G all edges have different colors. We call such a copy of L totally multicolored (TMC). In 7 among many other interesting results and problems, Burr, Erd?s, Graham, and T. Sós asked the following question: Let L be a connected bipartite graph which is not a star. Is it true then that In this article, we prove a slightly weaker statement, namely we show that the statement is true if L is a connected bipartite graph, which is not a complete bipartite graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 147–156, 2006     

Size Ramsey numbers of stars versus cliques

The size Ramsey number of two graphs and is the smallest integer such that there exists a graph on edges with the property that every red-blue colouring of the edges of yields a red copy of or a blue copy of . In 1981, Erdős observed that and he conjectured that this upper bound on is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: They proved the case . In 2001, Pikhurko showed that this conjecture is not true for and , by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given and .     

There exist graphs with super‐exponential Ramsey multiplicity constant

The Ramsey multiplicity M(G;n) of a graph G is the minimum number of monochromatic copies of G over all 2‐colorings of the edges of the complete graph K_n. For a graph G with a automorphisms, ν vertices, and E edges, it is natural to define the Ramsey multiplicity constant C(G) to be , which is the limit of the fraction of the total number of copies of G which must be monochromatic in a 2‐coloring of the edges of K_n. In 1980, Burr and Rosta showed that 0 ≥ C(G) ≤ 2^1?E for all graphs G, and conjectured that this upper bound is tight. Counterexamples of Burr and Rosta's conjecture were first found by Sidorenko and Thomason independently. Later, Clark proved that there are graphs G with E edges and 2^E?1C(G) arbitrarily small. We prove that for each positive integer E, there is a graph G with E edges and C(G) ≤ E^{?E/2 + o(E)}. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 89–98, 2008     

零和Ramsey数R(C_3,Z_3)的下界——(3)

Bialostocki和Dierker给出了古典Ramaey定理下列有趣的推广:设G是一个有m条边的图,整数k≥2,且k|m,Z_k表示k阶循环群。定义R(G,Z_k)表示一个极小整数t,使得对K_t的边的任意Z_k—染色(即一个泛函C:E(K_t)→Z_k),K_t中都存在一个同构于G的子图具有下列性质 sum from e∈E(G) C(e)≡0(mod k)。本文证明R(C_3,Z_3)≥11。     

A note on Ramsey size‐linear graphs

We show that if G is a Ramsey size‐linear graph and x,y ∈ V (G) then if we add a sufficiently long path between x and y we obtain a new Ramsey size‐linear graph. As a consequence we show that if G is any graph such that every cycle in G contains at least four consecutive vertices of degree 2 then G is Ramsey size‐linear. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 1–5, 2002     

Number of points on certain hyperelliptic curves defined over finite fields

For odd primes p and l such that the order of p modulo l is even, we determine explicitly the Jacobsthal sums _l(v), ψ_l(v), and ψ_2l(v), and the Jacobsthal–Whiteman sums and , over finite fields F_q such that . These results are obtained only in terms of q and l. We apply these results pertaining to the Jacobsthal sums, to determine, for each integer n1, the exact number of F_qⁿ-rational points on the projective hyperelliptic curves aY²Z^e−2=bX^e+cZ^e (abc≠0) (for e=l,2l), and aY²Z^l−1=X(bX^l+cZ^l) (abc≠0), defined over such finite fields F_q. As a consequence, we obtain the exact form of the ζ-functions for these three classes of curves defined over F_q, as rational functions in the variable t, for all distinct cases that arise for the coefficients a,b,c. Further, we determine the exact cases for the coefficients a,b,c, for each class of curves, for which the corresponding non-singular models are maximal (or minimal) over F_q.     

Transitive sets in Euclidean Ramsey theory

A finite set X in some Euclidean space Rn is called Ramsey if for any k there is a d such that whenever Rd is k-coloured it contains a monochromatic set congruent to X. This notion was introduced by Erd?s, Graham, Montgomery, Rothschild, Spencer and Straus, who asked if a set is Ramsey if and only if it is spherical, meaning that it lies on the surface of a sphere. This question (made into a conjecture by Graham) has dominated subsequent work in Euclidean Ramsey theory.In this paper we introduce a new conjecture regarding which sets are Ramsey; this is the first ever ‘rival’ conjecture to the conjecture above. Calling a finite set transitive if its symmetry group acts transitively—in other words, if all points of the set look the same—our conjecture is that the Ramsey sets are precisely the transitive sets, together with their subsets. One appealing feature of this conjecture is that it reduces (in one direction) to a purely combinatorial statement. We give this statement as well as several other related conjectures. We also prove the first non-trivial cases of the statement.Curiously, it is far from obvious that our new conjecture is genuinely different from the old. We show that they are indeed different by proving that not every spherical set embeds in a transitive set. This result may be of independent interest.     

含双参数的Ramsey数新上、下界公式

本文得到了含双参数x,y的Ramsey数的新上、下界公式,且初步研究了它的应用,证明了R（K6-e,K6）≤116和R（K6-e,K7）≤202.     

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     

A result in asymmetric Euclidean Ramsey theory

It is proved that if the points of the three-dimensional Euclidean space are coloured with red and blue, then there exist either two red points at unit distance, or six collinear blue points with distance one between any two consecutive points.     

Superfilters, Ramsey theory, and van der Waerden's Theorem

Superfilters are generalizations of ultrafilters, and capture the underlying concept in Ramsey-theoretic theorems such as van der Waerden's Theorem. We establish several properties of superfilters, which generalize both Ramsey's Theorem and its variants for ultrafilters on the natural numbers. We use them to confirm a conjecture of Kočinac and Di Maio, which is a generalization of a Ramsey-theoretic result of Scheepers, concerning selections from open covers. Following Bergelson and Hindman's 1989 Theorem, we present a new simultaneous generalization of the theorems of Ramsey, van der Waerden, Schur, Folkman–Rado–Sanders, Rado, and others, where the colored sets can be much smaller than the full set of natural numbers.     

Chromatic number is Ramsey distinguishing

A graph $G$ is Ramsey for a graph $H$ if every colouring of the edges of $G$ in two colours contains a monochromatic copy of $H$. Two graphs $H_1$ and $H_2$ are Ramsey equivalent if any graph $G$ is Ramsey for $H_1$ if and only if it is Ramsey for $H_2$. A graph parameter $s$ is Ramsey distinguishing if $s(H_1)\ne s(H_2)$ implies that $H_1$ and $H_2$ are not Ramsey equivalent. In this paper we show that the chromatic number is a Ramsey distinguishing parameter. We also extend this to the multicolour case and use a similar idea to find another graph parameter which is Ramsey distinguishing.     

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.     

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]}?)$.