Dennis Clemens
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Dennis Clemens has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Anita Liebenau
School of Mathematics and Statistics UNSW Sydney 2052 NSW Australia
4 shared publications - Asaf Ferber
School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv University 69978 Tel Aviv Israel
3 shared publications - Dan Hefetz
Department of Computer Science, Ariel University, Ariel, Israel
1 shared publication - Heidi Gebauer
Institute of Theoretical Computer Science, ETH Zurich, CH-8092, Switzerland
1 shared publication - Julia Ehrenmüller
Institut für Mathematik Technische Universität Hamburg-Harburg Germany
1 shared publication Michael Krivelevich
School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel
1 shared publication
Latest Publications
- Open Access
Keeping Avoider's graph almost acyclic
We consider biased $(1:b)$ Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if $b \geq 200 n \ln n$. By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non-$k$-colorability game, and the $K_t$-minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojakovi\'c, and Szab\'o. Moreover, we give a slight improvement for the lower bound in the non-planarity game.Open AccessKeeping Avoider's graph almost acyclic
We consider biased $(1:b)$ Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if $b \geq 200 n \ln n$. By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non-$k$-colorability game, and the $K_t$-minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojakovi\'c, and Szab\'o. Moreover, we give a slight improvement for the lower bound in the non-planarity game. - Open Access
The random graph intuition for the tournament game
In the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph on n vertices and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament T_k on k vertices. Maker wins if, at the end of the game, her digraph contains a copy of T_k; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for k = (2-o(1))log_2 n, 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))log_2 n Breaker can prevent that the underlying graph of Maker's graph contains 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 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 -- containing also the edges directed by Breaker -- possesses a copy of T_k. We prove that in that game Breaker has a winning strategy for k = (4+o(1))log_2 n.
Open AccessThe random graph intuition for the tournament game
In the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph on n vertices and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament T_k on k vertices. Maker wins if, at the end of the game, her digraph contains a copy of T_k; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for k = (2-o(1))log_2 n, 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))log_2 n Breaker can prevent that the underlying graph of Maker's graph contains 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 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 -- containing also the edges directed by Breaker -- possesses a copy of T_k. We prove that in that game Breaker has a winning strategy for k = (4+o(1))log_2 n.
- Open Access
Building spanning trees quickly in Maker-Breaker games
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, 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 non-trivial examples of families of trees which Maker cannot build in n-1 moves.
Open AccessBuilding spanning trees quickly in Maker-Breaker games
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, 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 non-trivial examples of families of trees which Maker cannot build in n-1 moves.
- 10 September 2012
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 21 (6) , 897-915
Fast Strategies In Maker–Breaker Games Played on Random Boards
In this paper we analyse classical Maker–Breaker games played on the edge set of a sparse random boardG~ n,p. We consider the Hamiltonicity game, the perfect matching game and thek-connectivity game. We prove that forp(n) ≥ polylog(n)/nthe boardG~ n,pis typically such that Maker can win these games asymptotically as fast as possible,i.e., withinn+o(n),n/2+o(n) andkn/2+o(n) moves respectively.
- 10 September 2012
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 21 (6) , 897-915
Fast Strategies In Maker–Breaker Games Played on Random Boards
In this paper we analyse classical Maker–Breaker games played on the edge set of a sparse random boardG~ n,p. We consider the Hamiltonicity game, the perfect matching game and thek-connectivity game. We prove that forp(n) ≥ polylog(n)/nthe boardG~ n,pis typically such that Maker can win these games asymptotically as fast as possible,i.e., withinn+o(n),n/2+o(n) andkn/2+o(n) moves respectively.
- Open Access
Fast strategies in Maker-Breaker games played on random boards
In this paper we analyze classical Maker-Breaker games played on the edge set of a sparse random board $G\sim \gnp$. We consider the Hamiltonicity game, the perfect matching game and the $k$-connectivity game. We prove that for $p(n)\geq \text{polylog}(n)/n$, the board $G\sim \gnp$ is typically such that Maker can win these games asymptotically as fast as possible, i.e. within $n+o(n)$, $n/2+o(n)$ and $kn/2+o(n)$ moves respectively.Open AccessFast strategies in Maker-Breaker games played on random boards
In this paper we analyze classical Maker-Breaker games played on the edge set of a sparse random board $G\sim \gnp$. We consider the Hamiltonicity game, the perfect matching game and the $k$-connectivity game. We prove that for $p(n)\geq \text{polylog}(n)/n$, the board $G\sim \gnp$ is typically such that Maker can win these games asymptotically as fast as possible, i.e. within $n+o(n)$, $n/2+o(n)$ and $kn/2+o(n)$ moves respectively.