Search

A graph F is Ramsey for a pair of graphs (G,H) if any red/blue-coloring of the edges of F yields a copy of G with all edges colored red or a copy of H with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case G = H, received considerable attention. This led to the open question whether there are connected graphs G and G\prime such that (G,G) and (G' ,G') are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several nontrivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form (T,Kt), where T is a tree and Kt is a complete graph. We show that if T belongs to a certain family of trees, including all nontrivial stars, then (T,Kt) is Ramsey equivalent to a family of pairs of the form (T,H), where H is obtained from Kt by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for (T,H) to be Ramsey equivalent to (T,Kt), H must have roughly this form. On the other hand, we prove that for many other trees T, including all odd-diameter trees, (T,Kt) is not equivalent to any such pair, not even to the pair (T,Kt K2), where Kt K2 is a complete graph Kt with a single edge attached. [ABSTRACT FROM AUTHOR]

A graph G is said to be q -Ramsey for a q -tuple of graphs (H1,...,Hq), denoted by G→q(H1,...,Hq), if every q -edge-coloring of G contains a monochromatic copy of Hi in color i for some i∈[q]. Let sq(H1,...,Hq) denote the smallest minimum degree of G over all graphs G that are minimal q -Ramsey for (H1,...,Hq) (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdős, and Lovász, who determined its value precisely for a pair of cliques. Over the past two decades the parameter sq has been studied by several groups of authors, their main focus being on the symmetric case, where Hi≅H for all i∈[q]. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles, and trees. We determine s2(H1,H2) when (H1,H2) is a pair of one clique and one tree, a pair of one clique and one cycle, and a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on sq(Cℓ,...,Cℓ,Kt,...,Kt) in terms of the size of the cliques t, the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed. [ABSTRACT FROM AUTHOR]

The size-Ramsey number of a graph F is the smallest number of edges in a graph G with the Ramsey property for F, that is, with the property that any 2-colouring of the edges of G contains a monochromatic copy of F. We prove that the size-Ramsey number of the grid graph on n × n vertices is bounded from above by n3+o(1). [ABSTRACT FROM AUTHOR]

For an integer q ⩾ 2, a graph G is called q-Ramsey for a graph H if every q-colouring of the edges of G contains a monochromatic copy of H. If G is q-Ramsey for H yet no proper subgraph of G has this property, then G is called q-Ramsey-minimal for H. Generalizing a statement by Burr, Nešetřil and Rödl from 1977, we prove that, for q ⩾ 3, if G is a graph that is not q-Ramsey for some graph H, then G is contained as an induced subgraph in an infinite number of q-Ramsey-minimal graphs for H as long as H is 3-connected or isomorphic to the triangle. For such H, the following are some consequences. For 2 ⩽ r < q, every r-Ramsey-minimal graph for H is contained as an induced subgraph in an infinite number of q-Ramsey-minimal graphs for H. For every q ⩾ 3, there are q-Ramsey-minimal graphs for H of arbitrarily large maximum degree, genus and chromatic number. The collection Mq(H) : H is 3-connected or K3 forms an antichain with respect to the subset relation, where Mq(H) denotes the set of all graphs that are q-Ramsey-minimal for H. We also address the question of which pairs of graphs satisfy Mq(H1) = Mq(Hq(H2) , in which case H1 and H2 are called q-equivalent. We show that two graphs H1 and H2 are q-equivalent for even q if they are 2-equivalent, and that in general q-equivalence for some q ⩾ 3 does not necessarily imply 2-equivalence. Finally we indicate that for connected graphs this implication may hold: results by Nešetřil and Rödl and by Fox, Grinshpun, Liebenau, Person and Szabó imply that the complete graph is not 2-equivalent to any other connected graph. We prove that this is the case for an arbitrary number of colours. [ABSTRACT FROM AUTHOR]

Given graphs G and H and a positive integer q, say that Gisq‐Ramsey forH, denoted G→(H)q, if every q‐coloring of the edges of G contains a monochromatic copy of H. The size‐Ramsey numberrˆ(H) of a graph H is defined to be rˆ(H)=min{∣E(G)∣:G→(H)2}. Answering a question of Conlon, we prove that, for every fixed k, we have rˆ(Pnk)=O(n), where Pnk is the kth power of the n‐vertex path Pn (ie, the graph with vertex set V(Pn) and all edges {u,v} such that the distance between u and v in Pn is at most k). Our proof is probabilistic, but can also be made constructive. [ABSTRACT FROM AUTHOR]

A uniform hypergraph H is called k-Ramsey for a hypergraph F if, no matter how one colours the edges of H with k colours, there is always a monochromatic copy of F. We say that H is k-Ramsey-minimal for F if H is k-Ramsey for F but every proper subhypergraph of H is not. Burr, Erdős and Lovasz studied various parameters of Ramsey-minimal graphs. In this paper we initiate the study of minimum degrees and codegrees of Ramsey-minimal 3-uniform hypergraphs. We show that the smallest minimum vertex degree over all k-Ramsey-minimal 3-uniform hypergraphs for Kt(3) is exponential in some polynomial in k and t. We also study the smallest possible minimum codegree over 2-Ramsey-minimal 3-uniform hypergraphs. [ABSTRACT FROM PUBLISHER]