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]

Maker-Breaker games are played on a hypergraph (X,\scrF), where \scrF \subseteq 2X 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 \scrF. These games are well studied when played on the complete graph Kn or on a random graph Gn,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 Gn,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 Gn,p, and we discuss the H-game when b = 1. [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]

We study ( a : a ) Maker–Breaker games played on the edge set of the complete graph on n vertices. In the following four games — perfect matching game, Hamilton cycle game, star factor game and path factor game, our goal is to determine the least number of moves which Maker needs in order to win these games. Moreover, for all games except for the star factor game, we show how first player can win in the strong version of these games. [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]

We consider biased ( 1 : b ) Walker–Breaker games: Walker and Breaker alternately claim edges of the complete graph K n , Walker taking one edge and Breaker claiming b edges in each round, with the constraint that Walker needs to choose her edges according to a walk. As questioned in a paper by Espig, Frieze, Krivelevich and Pegden, we study how long a cycle Walker is able to create and for which biases b Walker has a chance to create a cycle of given constant length. [ABSTRACT FROM AUTHOR]

In the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph Kn and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament Tk on k vertices. Maker wins if, at the end of the game, her digraph contains a copy of Tk; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for k = (2 − o(1))log2n, improving the constant factor in previous results of Beck and the second author. This is asymptotically tight since it is known that for k = (2 − o(1))log2n Breaker can prevent the underlying graph of Maker's digraph from containing a k-clique. Moreover, the precise value of our lower bound differs from the upper bound only by an additive constant of 12.We also discuss the question of whether the random graph intuition, which suggests that the threshold for k is asymptotically the same for the game played by two ‘clever’ players and the game played by two ‘random’ players, is supported by the tournament game. It will turn out that, while a straightforward application of this intuition fails, a more subtle version of it is still valid.Finally, we consider the orientation game version of the tournament game, where Maker wins the game if the final digraph – also containing the edges directed by Breaker – possesses a copy of Tk. We prove that in that game Breaker has a winning strategy for k = (4 + o(1))log2n. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]