Abstract. A graph [Formula: see text] is Ramsey for a pair of graphs [Formula: see text] if any red/blue-coloring of the edges of [Formula: see text] yields a copy of [Formula: see text] with all edges colored red or a copy of [Formula: see text] 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 [Formula: see text], received considerable attention. This led to the open question whether there are connected graphs [Formula: see text] and [Formula: see text] such that [Formula: see text] and [Formula: see text] 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 [Formula: see text], where [Formula: see text] is a tree and [Formula: see text] is a complete graph. We show that if [Formula: see text] belongs to a certain family of trees, including all nontrivial stars, then [Formula: see text] is Ramsey equivalent to a family of pairs of the form [Formula: see text], where [Formula: see text] is obtained from [Formula: see text] by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for [Formula: see text] to be Ramsey equivalent to [Formula: see text], [Formula: see text] must have roughly this form. On the other hand, we prove that for many other trees [Formula: see text], including all odd-diameter trees, [Formula: see text] is not equivalent to any such pair, not even to the pair [Formula: see text], where [Formula: see text] is a complete graph [Formula: see text] with a single edge attached.

Abstract. A graph [Formula: see text] is said to be [Formula: see text]-Ramsey for a [Formula: see text]-tuple of graphs [Formula: see text], denoted by [Formula: see text], if every [Formula: see text]-edge-coloring of [Formula: see text] contains a monochromatic copy of [Formula: see text] in color [Formula: see text] for some [Formula: see text]. Let [Formula: see text] denote the smallest minimum degree of [Formula: see text] over all graphs [Formula: see text] that are minimal [Formula: see text]-Ramsey for [Formula: see text] (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 [Formula: see text] has been studied by several groups of authors, their main focus being on the symmetric case, where [Formula: see text] for all [Formula: see text]. 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 [Formula: see text] when [Formula: see text] 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 [Formula: see text] in terms of the size of the cliques [Formula: see text], 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.

Given any graph $H$, a graph $G$ is said to be $q$-Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$. Such a graph $G$ is said to be minimal $q$-Ramsey for $H$ if additionally no proper subgraph $G'$ of $G$ is $q$-Ramsey for $H$. In 1976, Burr, Erdös, and Lovász initiated the study of the parameter $s_q(H)$, defined as the smallest minimum degree among all minimal $q$-Ramsey graphs for $H$. In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$-Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$-abundant. Among other results, we prove that every cycle is $s_q$-abundant for any integer $q\geq 2$. We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr and co-authors and Fox and co-authors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.

Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board $X$, and Maker wins the game if she is able to occupy any winning set $F \in \mathcal{F}$. These games are well studied when played on the complete graph $K_n$ or on a random graph $G_{n,p}$. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph $G_\alpha$ with minimum degree at least $\alpha n$ and a binomial random graph $G_{n,p}$. Depending on $\alpha$ and Breaker's bias $b$ we determine the order of the threshold probability for winning the Hamiltonicity game and the $k$-connectivity game on $G_{\alpha}\cup G_{n,p}$, and we discuss the $H$-game when $b=1$.

For a tree $T$ on $n$ vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on $n$ vertices, which Maker wins as soon as the graph she builds contains a copy of $T$. We prove that if $T$ has bounded maximum degree and $n$ is sufficiently large, then Maker can win this game within $n+1$ moves. Moreover, we prove that Maker can build almost every tree on $n$ vertices in $n-1$ moves and provide nontrivial examples of families of trees which Maker cannot build in $n-1$ moves.