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]

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]

We initiate the study of a new variant of the Maker-Breaker positional game, which we call multistage game. Given a hypergraph H = (X , F) and a bias b ≥ 1 , the (1 : b) multistage Maker-Breaker game on H is played in several stages as follows. Each stage is played as a usual (1 : b) Maker-Breaker game, until all the elements of the board get claimed by one of the players, with the first stage being played on H. In every subsequent stage, the game is played on the board reduced to the elements that Maker claimed in the previous stage, and with the winning sets reduced to those fully contained in the new board. The game proceeds until no winning sets remain, and the goal of Maker is to prolong the duration of the game for as many stages as possible. In this paper we estimate the maximum duration of the (1 : b) multistage Maker-Breaker game, for biases b subpolynomial in n , for some standard graph games played on the edge set of K n : the connectivity game, the Hamilton cycle game, the non- k -colorability game, the pancyclicity game and the H -game. While the first three games exhibit a probabilistic intuition, it turns out that the last two games fail to do so. [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]

The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann. [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]

Motivated by a question of Grinblat, we study the minimal number v ( n ) that satisfies the following. If A 1 , … , A n are equivalence relations on a set X such that for every i ∈ [ n ] there are at least v ( n ) elements whose equivalence classes with respect to A i are nontrivial, then A 1 , … , A n contain a rainbow matching, i.e. there exist 2 n distinct elements x 1 , y 1 , … , x n , y n ∈ X with x i ∼ A i y i for each i ∈ [ n ] . Grinblat asked whether v ( n ) = 3 n − 2 for every n ≥ 4 . The best-known upper bound was v ( n ) ≤ 16 n / 5 + O ( 1 ) due to Nivasch and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that v ( n ) = 3 n + o ( n ) . [ABSTRACT FROM AUTHOR]

In the Oriented-cycle game, introduced by Bollobás and Szabó [7] , two players, called OMaker and OBreaker, alternately direct edges of K n . OMaker directs exactly one previously undirected edge, whereas OBreaker is allowed to direct between one and b previously undirected edges. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. Bollobás and Szabó [7] conjectured that for a bias as large as n − 3 OMaker has a winning strategy if OBreaker must take exactly b edges in each round. It was shown recently by Ben-Eliezer, Krivelevich and Sudakov [6] , that OMaker has a winning strategy for this game whenever b < n / 2 − 1 . In this paper, we show that OBreaker has a winning strategy whenever b > 5 n / 6 + 1 . Moreover, in case OBreaker is required to direct exactly b edges in each move, we show that OBreaker wins for b ⩾ 19 n / 20 , provided that n is large enough. This refutes the conjecture by Bollobás and Szabó. [ABSTRACT FROM AUTHOR]

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]

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]

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]