34 results
Now showing1 - 10 of 34
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Constructions for positional games and applications to domination games(Australian National University, 2026-08-28); ; ; We present constructions regarding the general behaviour of biased positional games, and amongst others show that the outcome of such a game can differ in an arbitrary way depending on which player starts the game, and that fair biased games can behave highly non-monotonic. We construct a gadget that helps to transfer such results to Maker-Breaker domination games, and by this we extend a recent result by Gledel, Iršič, and Klavžar, regarding the length of such games. Additionally, we introduce Waiter-Client dominations games, give tight results when they are played on trees or cycles, and using our transference gadget we show that in general the length of such games can differ arbitrarily from the length of their Maker-Breaker analogue.Publicationtype: Journal Article9 1 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Creating spanning trees in waiter-client games(Australian National University, 2025-08-22); ; ; For a positive integer n and a tree Tn on n vertices, we consider an unbiased Waiter-Client game WC(n, Tn) played on the complete graph Kn, in which Waiter’s goal is to force Client to build a copy of Tn. We prove that for every constant c < 1/3, if ∆(Tn) ≤ cn and n is sufficiently large, then Waiter has a winning strategy in WC(n, Tn). On the other hand, we show that there exist a positive constant c′ < 1/2 and a family of trees Tn with ∆(Tn) ≤ c′n such that Client has a winning strategy in the WC(n, Tn) game for every n sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game.Publicationtype: Journal Article9 21 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Maker playing against an invisible Breaker(2025-07-30); ; ; ; We initiate the study of the phantom version of Maker-Breaker positional games. In a phantom game, the moves of one of the players are hidden from the other player, who still has the complete information. We look at the biased a : b Maker-PhantomBreaker games where the board is the edge set of the complete graph on n vertices, Kn, and Maker has no information about PhantomBreaker’s choices of edges. We give randomized strategies for both players in four classical games: connectivity game, perfect matching game, mindegree-k game and Hamiltonicity game. In particular, we focus on characterizing all biases pa : bq for which Maker wins asymptotically almost surely.Publicationtype: Preprint13 61 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Ramsey simplicity of random graphs(Cambridge University Press (CUP), 2025); ; ; 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ős, and Lovász 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 δ(G) ≥ q(δ(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 lognn p 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 first extend Grinshpun’s result by showing that G(n, p) is not just 2-Ramsey simple, but is in fact q-Ramsey simple for any q = q(n), provided p n−1 or lognn p n−2/3. Next, when p lognn1/2, we find that G(n, p) is not q-Ramsey simple for any q ≥ 2. Finally, we uncover some interesting behaviour for intermediate edge probabilities. When n−2/3 p n−1/2, we find that there is some finite threshold q = q (H), depending on the structure of the instance H ∼ G(n, p) of the random graph, such that H is q-Ramsey simple if and only if q ≤ q. Aside from a couple of logarithmic factors, this resolves the qualitative nature of the Ramsey simplicity of the random graph over the full spectrum of edge probabilities.Publicationtype: Journal Article13 22 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Tree universality in positional games(Cambridge University Press (CUP), 2025); ; ; In this paper we consider positional games where the winning sets are edge sets of tree-universal graphs. Specifically, we show that in the unbiased Maker-Breaker game on the edges of the complete graph <![CDATA[ $K_n$ ]]>, Maker has a strategy to claim a graph which contains copies of all spanning trees with maximum degree at most <![CDATA[ $cn/\log (n)$ ]]>, for a suitable constant <![CDATA[ $c$ ]]> and <![CDATA[ $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.Publicationtype: Journal Article19 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Walker-Breaker games on Gn,pThe 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ár studied the threshold bias for the Connector Breaker connectivity game on a complete graph Kn, 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 ∼ Gn,p is of order n−2/3+o(1). We extent this result further to WalkerBreaker games and prove that this probability is also enough for Walker to create a Hamilton cycle.Publicationtype: Journal Article15 35 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Ramsey equivalence for asymmetric pairs of graphs(Society for Industrial & Applied Mathematics (SIAM), 2024); ; ; 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\prime, G\prime) 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 \cdot K2), where Kt \cdot K2 is a complete graph Kt with a single edge attached.Publicationtype: Journal Article5 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Multistage positional games(Elsevier, 2023-09); ; ; ; 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 Kn: 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.Publicationtype: Journal Article50 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Perfectly packing graphs with bounded degeneracy and many leaves(2023-06); ; ; 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(Formula Presented.)., and in addition Ω(n) of them have at most (1 − Ω(1))n vertices and Ω(n) leaves. This proves Ringel’s conjecture and the Gyárfás Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees, respectively).Publicationtype: Journal Article79 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , On the minimum degree of minimal Ramsey graphs for cliques versus cycles(Soc., 2023-01); ; ; ; 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, Erdos, and Lovasz, 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.Publicationtype: Journal Article33