Search

For a positive integer $n$ and a tree $T_n$ on $n$ vertices, we consider an unbiased Waiter-Client game $\textrm{WC}(n,T_n)$ played on the complete graph~$K_n$, in which Waiter's goal is to force Client to build a copy of $T_n$. We prove that for every constant $c<1/3$, if $\Delta(T_n)\le cn$ and $n$ is sufficiently large, then Waiter has a winning strategy in $\textrm{WC}(n,T_n)$. On the other hand, we show that there exist a positive constant $c'<1/2$ and a family of trees $T_{n}$ with $\Delta(T_n)\le c'n$ such that Client has a winning strategy in the $\textrm{WC}(n,T_n)$ game for every $n$ sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game.

In this paper we consider positional games where the winning sets are tree universal graphs. Specifically, we show that in the unbiased Maker-Breaker game on the complete graph $K_n$, Maker has a strategy to occupy a graph which contains copies of all spanning trees with maximum degree at most $cn/\log(n)$, for a suitable constant $c$ and $n$ being large enough. We also prove an analogous result for Waiter-Client games. Both of our results show that the building player can play at least as good as suggested by the random graph intuition. Moreover, they improve on a special case of earlier results by Johannsen, Krivelevich, and Samotij as well as Han and Yang for Maker-Breaker games.

The Maker-Breaker connectivity game and Hamilton cycle game belong to the best studied games in positional games theory, including results on biased games, games on random graphs and fast winning strategies. Recently, the Connector-Breaker game variant, in which Connector has to claim edges such that her graph stays connected throughout the game, as well as the Walker-Breaker game variant, in which Walker has to claim her edges according to a walk, have received growing attention. For instance, London and Pluh\'ar studied the threshold bias for the Connector-Breaker connectivity game on a complete graph $K_n$, and showed that there is a big difference between the cases when Maker's bias equals $1$ or $2$. Moreover, a recent result by the first and third author as well as Kirsch shows that the threshold probability $p$ for the $(2:2)$ Connector-Breaker connectivity game on a random graph $G\sim G_{n,p}$ is of order $n^{-2/3+o(1)}$. We extent this result further to Walker-Breaker games and prove that this probability is also enough for Walker to create a Hamilton cycle.

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'$ such that $(G,G)$ and $(G',G')$ are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several non-trivial 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,K_t)$, where $T$ is a tree and $K_t$ is a complete graph. We show that, if $T$ belongs to a certain family of trees, including all non-trivial stars, then $(T,K_t)$ is Ramsey equivalent to a family of pairs of the form $(T,H)$, where $H$ is obtained from $K_t$ by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for $(T,H)$ to be Ramsey equivalent to $(T,K_t)$, $H$ must have roughly this form. On the other hand, we prove that for many other trees $T$, including all odd-diameter trees, $(T,K_t)$ is not equivalent to any such pair, not even to the pair $(T, K_t\cdot K_2)$, where $K_t\cdot K_2$ is a complete graph $K_t$ with a single edge attached., Comment: 22 pages, 7 figures

We initiate the study of a new variant of the Maker-Breaker positional game, which we call multistage game. Given a hypergraph $\mathcal{H}=(\mathcal{X},\mathcal{F})$ and a bias $b \ge 1$, the $(1:b)$ multistage Maker-Breaker game on $\mathcal{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 $\mathcal{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.

A graph $G$ is $q$-Ramsey for another graph $H$ if in any $q$-edge-colouring of $G$ there is a monochromatic copy of $H$, and the classic Ramsey problem asks for the minimum number of vertices in such a graph. This was broadened in the seminal work of Burr, Erd\H{o}s, and Lov\'asz to the investigation of other extremal parameters of Ramsey graphs, including the minimum degree. It is not hard to see that if $G$ is minimally $q$-Ramsey for $H$ we must have $\delta(G) \ge q(\delta(H) - 1) + 1$, and we say that a graph $H$ is $q$-Ramsey simple if this bound can be attained. Grinshpun showed that this is typical of rather sparse graphs, proving that the random graph $G(n,p)$ is almost surely $2$-Ramsey simple when $\frac{\log n}{n} \ll p \ll n^{-2/3}$. In this paper, we explore this question further, asking for which pairs $p = p(n)$ and $q = q(n,p)$ we can expect $G(n,p)$ to be $q$-Ramsey simple. We resolve the problem for a wide range of values of $p$ and $q$; in particular, we uncover some interesting behaviour when $n^{-2/3} \ll p \ll n^{-1/2}$., Comment: 29 pages, 2 figures

A graph $G$ is said to be $q$-Ramsey for a $q$-tuple of graphs $(H_1,\ldots,H_q)$, denoted by $G\to_q(H_1,\ldots,H_q)$, if every $q$-edge-coloring of $G$ contains a monochromatic copy of $H_i$ in color $i,$ for some $i\in[q]$. Let $s_q(H_1,\ldots,H_q)$ denote the smallest minimum degree of $G$ over all graphs $G$ that are minimal $q$-Ramsey for $(H_1,\ldots,H_q)$ (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erd\H{o}s and Lov\'asz, who determined its value precisely for a pair of cliques. Over the past two decades the parameter $s_q$ has been studied by several groups of authors, the main focus being on the symmetric case, where $H_i\cong H$ for all $i\in [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 $s_2(H_1,H_2)$ when $(H_1,H_2)$ is a pair of one clique and one tree, a pair of one clique and one cycle, and when it is a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on $s_q(C_\ell,\ldots,C_\ell,K_t,\ldots,K_t)$ 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.

We prove that there is $c>0$ such that for all sufficiently large $n$, if $T_1,\dots,T_n$ are any trees such that $T_i$ has $i$ vertices and maximum degree at most $cn/\log n$, then $\{T_1,\dots,T_n\}$ packs into $K_n$. Our main result actually allows to replace the host graph $K_n$ by an arbitrary quasirandom graph, and to generalize from trees to graphs of bounded degeneracy that are rich in bare paths, contain some odd degree vertices, and only satisfy much less stringent restrictions on their number of vertices., Comment: 157 pages, 4 figures; small improvements throughout compared to the previous version

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$. Furthermore, we give optimal results for the Waiter-Client versions of all mentioned games., Comment: 44 pages

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$. Further, 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\H{o}s, and Lov\'asz 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 et al. and Fox et al. To prove our results and construct suitable minimal Ramsey graphs, we develop certain new gadget graphs, called pattern gadgets, which generalize and extend earlier constructions that have proven useful in the study of minimal Ramsey graphs. These new gadgets might be of independent interest.

Waiter-Client games are played on some hypergraph $(X,\mathcal{F})$, where $\mathcal{F}$ denotes the family of winning sets. For some bias $b$, during each round of such a game Waiter offers to Client $b+1$ elements of $X$, of which Client claims one for himself while the rest go to Waiter. Proceeding like this Waiter wins the game if she forces Client to claim all the elements of any winning set from $\mathcal{F}$. In this paper we study fast strategies for several Waiter-Client games played on the edge set of the complete graph, i.e. $X=E(K_n)$, in which the winning sets are perfect matchings, Hamilton cycles, pancyclic graphs, fixed spanning trees or factors of a given graph., Comment: 38 pages

By now, the Maker-Breaker connectivity game on a complete graph $K_n$ or on a random graph $G\sim G_{n,p}$ is well studied. Recently, London and Pluh\'ar suggested a variant in which Maker always needs to choose her edges in such a way that her graph stays connected. By their results it follows that for this connected version of the game, the threshold bias on $K_n$ and the threshold probability on $G\sim G_{n,p}$ for winning the game drastically differ from the corresponding values for the usual Maker-Breaker version, assuming Maker's bias to be $1$. However, they observed that the threshold biases of both versions played on $K_n$ are still of the same order if instead Maker is allowed to claim two edges in every round. Naturally, this made London and Pluh\'ar ask whether a similar phenomenon can be observed when a $(2:2)$ game is played on $G_{n,p}$. We prove that this is not the case, and determine the threshold probability for winning this game to be of size $n^{-2/3+o(1)}$., Comment: 33 pages, 3 figures

We prove that one can perfectly pack degenerate graphs into complete or dense $n$-vertex quasirandom graphs, provided that all the degenerate graphs have maximum degree $o(\frac{n}{\log n})$, and in addition $\Omega(n)$ of them have at most $(1-\Omega(1))n$ vertices and $\Omega(n)$ leaves. This proves Ringel's conjecture and the Gy\'arf\'as Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees, respectively)., Comment: 51 pages

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\times n$ vertices is bounded from above by $n^{3+o(1)}$., Comment: 21 pages, second version addresses changes arising from the referee report and comments from Thomas Lesgourgues

A Hamilton Berge cycle of a hypergraph on $n$ vertices is an alternating sequence $(v_1, e_1, v_2, \ldots, v_n, e_n)$ of distinct vertices $v_1, \ldots, v_n$ and distinct hyperedges $e_1, \ldots, e_n$ such that $\{v_1,v_n\}\subseteq e_n$ and $\{v_i, v_{i+1}\} \subseteq e_i$ for every $i\in [n-1]$. We prove the following Dirac-type theorem about Berge cycles in the binomial random $r$-uniform hypergraph $H^{(r)}(n,p)$: for every integer $r \geq 3$, every real $\gamma>0$ and $p \geq \frac{\ln^{17r} n}{n^{r-1}}$ asymptotically almost surely, every spanning subgraph $H \subseteq H^{(r)}(n,p)$ with minimum vertex degree $\delta_1(H) \geq \left(\frac{1}{2^{r-1}} + \gamma\right) p \binom{n}{r-1}$ contains a Hamilton Berge cycle. The minimum degree condition is asymptotically tight and the bound on $p$ is optimal up to some polylogarithmic factor., Comment: 16 pages, an extended abstract of this paper appeared in the Proceedings of the Discrete Mathematics Days 2016

For an integer $q\ge 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$. Generalising a statement by Burr, Ne\v{s}et\v{r}il and R\"odl from 1977 we prove that, for $q\ge 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. (1) For $2\le 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$. (2) For every $q\ge 3$, there are $q$-Ramsey-minimal graphs for $H$ of arbitrarily large maximum degree, genus, and chromatic number. (3) The collection $\{{\cal M}_q(H) : H \text{ is 3-connected or } K_3\}$ forms an antichain with respect to the subset relation, where ${\cal M}_q(H)$ denotes the set of all graphs that are $q$-Ramsey-minimal for $H$. We also address the question which pairs of graphs satisfy ${\cal M}_q(H_1)={\cal M}_q(H_2)$, in which case $H_1$ and $H_2$ are called $q$-equivalent. We show that two graphs $H_1$ and $H_2$ are $q$-equivalent for even $q$ if they are $2$-equivalent, and that in general $q$-equivalence for some $q\ge 3$ does not necessarily imply $2$-equivalence. Finally we indicate that for connected graphs this implication may hold: Results by Ne\v{s}et\v{r}il and R\"odl and by Fox, Grinshpun, Liebenau, Person and Szab\'o 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.

Given graphs $G$ and $H$ and a positive integer $q$ say that $G$ is $q$-Ramsey for $H$, denoted $G\rightarrow (H)_q$, if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The size-Ramsey number $\hat{r}(H)$ of a graph $H$ is defined to be $\hat{r}(H)=\min\{|E(G)|\colon G\rightarrow (H)_2\}$. Answering a question of Conlon, we prove that, for every fixed $k$, we have $\hat{r}(P_n^k)=O(n)$, where $P_n^k$ is the $k$-th power of the $n$-vertex path $P_n$ (i.e. , the graph with vertex set $V(P_n)$ and all edges $\{u,v\}$ such that the distance between $u$ and $v$ in $P_n$ is at most $k$). Our proof is probabilistic, but can also be made constructive.

The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erd\H{o}s-Rothschild problem, introduced in 1974 by Erd\H{o}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\H{o}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\H{o}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\H{o}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\H{o}s-Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann., Comment: 31 pages

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 Red can win in the strong version of these games., Comment: An extended abstract appears in the proceedings of the EuroComb 2015

Motivated by a question of Grinblat, we study the minimal number $\mathfrak{v}(n)$ that satisfies the following. If $A_1,\ldots, A_n$ are equivalence relations on a set $X$ such that for every $i\in[n]$ there are at least $\mathfrak{v}(n)$ elements whose equivalence classes with respect to $A_i$ are nontrivial, then $A_1, \ldots, A_n$ contain a rainbow matching, i.e. there exist $2n$ distinct elements $x_1,y_1,\ldots,x_n,y_n\in X$ with $x_i\sim_{A_i} y_i$ for each $i\in [n]$. Grinblat asked whether $\mathfrak{v}(n) = 3n-2$ for every $n\geq 4$. The best-known upper bound was $\mathfrak{v}(n) \leq 16n/5 + \mathcal{O}(1)$ due to Nivash and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that $\mathfrak{v}(n) = 3n+o(n)$.

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., Comment: 23 pages, to appear in Discrete Mathematics

We study the Maker-Breaker tournament game played on the edge set of a given graph $G$. Two players, Maker and Breaker claim unclaimed edges of $G$ in turns, and Maker wins if by the end of the game she claims all the edges of a pre-defined goal tournament. Given a tournament $T_k$ on $k$ vertices, we determine the threshold bias for the $(1:b)$ $T_k$-tournament game on $K_n$. We also look at the $(1:1)$ $T_k$-tournament game played on the edge set of a random graph ${\mathcal{G}_{n,p}}$ and determine the threshold probability for Maker's win. We compare these games with the clique game and discuss whether a random graph intuition is satisfied.

A conjecture by Aharoni and Berger states that every family of $n$ matchings of size $n+1$ in a bipartite multigraph contains a rainbow matching of size $n$. In this paper we prove that matching sizes of $(3/2 + o(1)) n$ suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best known one in case we only aim to find a rainbow matching of size $n-1$. This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.

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