Source author record

Alon Naor

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Avoider-Enforcer star games

In this paper, we study $(1 : b)$ Avoider-Enforcer games played on the edge set of the complete graph on $n$ vertices. For every constant $k\geq 3$ we analyse the $k$ -star game, where Avoider tries to avoid claiming $k$ edges incident to the same vertex. We analyse both versions of Avoider-Enforcer games -- the strict and the monotone -- and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases $f^{mon}_\mathcal{F}$ , $f^-_\mathcal{F}$ and $f^+_\mathcal{F}$ , where $\mathcal{F}$ is the hypergraph of the game.

preprint2015arXiv

On saturation games

A graph $G = (V,E)$ is said to be saturated with respect to a monotone increasing graph property ${\mathcal P}$ , if $G \notin {\mathcal P}$ but $G \cup \{e\} \in {\mathcal P}$ for every $e \in \binom{V}{2} \setminus E$ . The saturation game $(n, {\mathcal P})$ is played as follows. Two players, called Mini and Max, progressively build a graph $G \subseteq K_n$ , which does not satisfy ${\mathcal P}$ . Starting with the empty graph on $n$ vertices, the two players take turns adding edges $e \in \binom{V(K_n)}{2} \setminus E(G)$ , for which $G \cup \{e\} \notin {\mathcal P}$ , until no such edge exists (i.e. until $G$ becomes ${\mathcal P}$ -saturated), at which point the game is over. Max's goal is to maximize the length of the game, whereas Mini aims to minimize it. The score of the game, denoted by $s(n, {\mathcal P})$ , is the number of edges in $G$ at the end of the game, assuming both players follow their optimal strategies. We prove lower and upper bounds on the score of games in which the property the players need to avoid is being $k$ -connected, having chromatic number at least $k$ , and admitting a matching of a given size. In doing so we demonstrate that the score of certain games can be as large as the Turán number or as low as the saturation number of the respective graph property. We also demonstrate that the score might strongly depend on the identity of the first player to move.

preprint2013arXiv

Avoider-Enforcer games played on edge disjoint hypergraphs

We analyze Avoider-Enforcer games played on edge disjoint hypergraphs, providing an analog of the classic and well known game $Box$ , due to Chvátal and Erdős. We consider both strict and monotone versions of Avoider-Enforcer games, and for each version we give a sufficient condition to win for each player. We also present applications of our results to several general Avoider-Enforcer games.

preprint2013arXiv

Component Games on Regular Graphs

We study the (1:b) Maker-Breaker component game, played on the edge set of a d-regular graph. Maker's aim in this game is to build a large connected component, while Breaker's aim is to not let him do so. For all values of Breaker's bias b, we determine whether Breaker wins (on any d-regular graph) or Maker wins (on almost every d-regular graph) and provide explicit winning strategies for both players. To this end, we prove an extension of a theorem by Gallai-Hasse-Roy-Vitaver about graph orientations without long directed simple paths.

preprint2012arXiv

Biased Games On Random Boards

In this paper we analyze biased Maker-Breaker games and Avoider-Enforcer games, both played on the edge set of a random board $G\sim \gnp$. In Maker-Breaker games there are two players, denoted by Maker and Breaker. In each round, Maker claims one previously unclaimed edge of $G$ and Breaker responds by claiming $b$ previously unclaimed edges. We consider the Hamiltonicity game, the perfect matching game and the $k$ -vertex-connectivity game, where Maker's goal is to build a graph which possesses the relevant property. Avoider-Enforcer games are the reverse analogue of Maker-Breaker games with a slight modification, where the two players claim at least 1 and at least $b$ previously unclaimed edges per move, respectively, and Avoider aims to avoid building a graph which possesses the relevant property. Maker-Breaker games are known to be "bias-monotone", that is, if Maker wins the $(1,b)$ game, he also wins the $(1,b-1)$ game. Therefore, it makes sense to define the critical bias of a game, $b^*$ , to be the "breaking point" of the game. That is, Maker wins the $(1,b)$ game whenever $b\leq b^*$ and loses otherwise. An analogous definition of the critical bias exists for Avoider-Enforcer games: here, the critical bias of a game $b^*$ is such that Avoider wins the $(1,b)$ game for every $b > b^*$ , and loses otherwise. We prove that, for every $p=ω(\frac{\ln n}{n})$ , $G\sim\gnp$ is typically such that the critical bias for all the aforementioned Maker-Breaker games is asymptotically $b^*=\frac{np}{\ln n}$ . We also prove that in the case $p=Θ(\frac{\ln n}{n})$ , the critical bias is $b^*=Θ(\frac{np}{\ln n})$ . These results settle a conjecture of Stojaković and Szabó. For Avoider-Enforcer games, we prove that for $p=Ω(\frac{\ln n}{n})$ , the critical bias for all the aforementioned games is $b^*=Θ(\frac{np}{\ln n})$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.